数据结构练习题（链表-p66）

1对给定的带头结点的单链表 head,编写一个删除head中值为 x的结点的直接前驱
结点的算法(假设链表中最多只有一个值为×的结点)。

思路：要删除x的直接前驱，需要判断其直接前驱的前一个结点的情况

• 初始检查：如果链表为空或只有一个节点（即只有头节点），直接返回。
• 遍历链表：
  • current 从第一个实际节点开始遍历。
  • prev 初始为头节点，用于保存当前节点的前一个节点。
  • prev_prev 初始为空，用于保存前一个节点的前一个节点。

• 删除操作：
  • 如果找到值为 x 的节点，根据 prev_prev 是否为空来决定如何调整链表结构。
  • 如果 prev_prev 为空，说明前驱节点是头节点后的第一个节点，直接将头节点的 next 指针指向当前节点。
  • 否则，将 prev_prev 的 next 指针指向当前节点。
  • 释放前驱节点的内存。
  • 删除操作完成后，退出循环。

代码：

struct ListNode* delete_predecessor_of_x(struct ListNode* head, int x) {if (!head || !head->next) {// 如果链表为空或只有一个节点（即只有头节点），直接返回return head;}struct ListNode* current = head->next;  // 当前节点，从第一个实际节点开始struct ListNode* prev = head;  // 前一个节点，初始为头节点struct ListNode* prev_prev = NULL;  // 前前一个节点，初始为空while (current) {if (current->val == x) {// 找到了值为 x 的节点if (!prev_prev) {// 如果前驱节点是头节点后的第一个节点head->next = current;  // 跳过前驱节点，直接连接到当前节点} else {prev_prev->next = current;  // 跳过前驱节点，连接到当前节点}free(prev);  // 释放前驱节点的内存break;  // 删除操作完成，退出循环}prev_prev = prev;  // 更新前前一个节点prev = current;  // 更新前一个节点current = current->next;  // 移动到下一个节点}return head;  // 返回修改后的链表头节点
}

2有一个单链表head,编写函数从单链表中删除自第i个结点起的k个结点

思路：

1. 边界条件检查: 在执行删除操作之前，我们需要检查：

   • 单链表是否为空。
   • i 是否小于 0（即无效索引）。
   • k 是否小于或等于 0（即无效删除数）。

2. 找到第 i 个节点: 我们需要遍历链表，以找到第 i 个节点的位置。设定一个指针 current 来遍历，另一个指针 prev 用于记录 current 的前一个节点。

3. 删除节点: 从第 i 个节点开始，逐个删除后面 k 个节点。每次删除一个节点时，更新 current 指针以指向下一个节点。

4. 更新链接: 删除操作完成后，需要小心地更新指向链表的指针。如果我们删除的是头节点，则需要更新 head，否则将 i-1 节点的 next 指针指向 i+k 的节点。

代码：

void deleteNodes(ListNode* head, int i, int k) {if (!head || i < 0 || k <= 0) return;  // 无效输入处理ListNode *prev = NULL;ListNode *current = head;// 移动到第 i 个节点for (int j = 0; j < i && current; ++j) {prev = current;current = current->next;}// 如果 current 为空，说明链表长度不足 i 个节点if (!current) return;// 删除 k 个节点for (int j = 0; j < k && current; ++j) {ListNode *temp = current;current = current->next;delete temp;  // 释放内存}// 连接第 i-1 个节点和第 i+k 个节点if (prev) {prev->next = current;} else {head = current;  // 如果删除的是头节点，更新 head}
}

3有一个单链表（不同结点数据域的值可能相同)，其头指针为head,编写函数计算 值为×的结点个数。

思路：遍历链表，统计值为 x 的节点个数。

代码：

//计算值为 x 的节点个数的函数
int countNodesValue(struct ListNode* head, int x) {int count = 0; // 初始化计数器struct ListNode* current = head; // 从链表头开始遍历// 遍历链表while (current != NULL) {if (current->val == x) { // 如果当前节点的值等于 xcount++; // 计数器加一}current = current->next; // 移动到下一个节点}return count; // 返回总计数
}

4.有两个单向循环链表，链头指针分别为 headl和head2，编写一个函数将链表
headl原地连接到链表head2之后，连接后的链表仍是单向循环链表

思路：

1. 找到链表的尾节点 (findTail 函数):

   • 输入: 链表的头节点 head。
   • 输出: 链表的尾节点（即指向头节点的前一个节点）。
   • 逻辑:
     • 如果链表为空 (head 为 NULL)，则返回 NULL。
     • 初始化一个指针 tail 指向 head，用于遍历链表。
     • 使用一个 while 循环遍历链表，条件是 tail->next != head。当 tail->next 指向 head 时，tail 就是尾节点，循环结束。
     • 返回 tail，即整个链表的尾节点。

2. 连接两个单向循环链表 (connectLists 函数):

   • 输入: 指向链表 head1 的指针（struct ListNode** head1），链表 head2 的头节点指针（struct ListNode* head2）。
   • 逻辑:
     • 首先检查 head1 是否为空：
       • 如果为空，直接将 head2 赋值给 head1，即相当于连接后 head1 完全指向 head2，形成一个循环。
     • 如果 head2 为空，则不需要连接，直接返回。
     • 找到 head1 的尾节点 tail1 和 head2 的尾节点 tail2：
       • tail1 用于将 head1 的最后一个节点连接到 head2 的头节点。
       • tail2 用于将 head2 的最后一个节点连接回 head1 的头节点。
     • 连接操作：
       • tail1->next = head2; 将 head1 的尾节点连接到 head2 的头节点。
       • tail2->next = *head1; 将 head2 的尾节点连接回 head1 的头节点，形成一个完整且循环的链表。

代码：

// 找到链表的尾节点
struct ListNode* findTail(struct ListNode* head) {if (head == NULL) return NULL; // 如果链表为空，返回 NULLstruct ListNode* tail = head; // 初始化尾节点为头节点// 遍历链表，直到找到指向头节点的节点，即尾节点while (tail->next != head) {tail = tail->next; // 移动到下一个节点}return tail; // 返回链表的尾节点
}// 连接两个单向循环链表  **head1二级指针
void connectLists(struct ListNode**head1, struct ListNode* head2) {if (*head1 == NULL) {// 如果 head1 为空，直接将 head2 赋值给 head1*head1 = head2; // 此时可以将 head1 直接指向 head2，因此无需再进行连接return;}if (head2 == NULL) {// 如果 head2 为空，不需要做任何操作return; // 直接返回，无需连接}// 找到 head1 的尾节点struct ListNode* tail1 = findTail(*head1); // 找到 head2 的尾节点struct ListNode* tail2 = findTail(head2); // 将 head1 的尾节点指向 head2 的头节点tail1->next = head2; // 将 head2 的尾节点指向 head1 的头节点tail2->next = *head1; 
}

完整代码：

#include <stdio.h>
#include <stdlib.h>// 定义单向循环链表节点结构体
struct ListNode {int val; // 节点值struct ListNode* next; // 指向下一个节点的指针
};// 创建新节点的函数
struct ListNode* createNode(int value) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));newNode->val = value;newNode->next = newNode; // 单向循环链表，指向自身return newNode;
}// 找到链表的尾节点
struct ListNode* findTail(struct ListNode* head) {if (head == NULL) return NULL;struct ListNode* tail = head;while (tail->next != head) {tail = tail->next;}return tail;
}// 连接两个单向循环链表
void connectLists(struct ListNode** head1, struct ListNode* head2) {if (*head1 == NULL) {// 如果 head1 为空，直接将 head2 赋值给 head1*head1 = head2;return;}if (head2 == NULL) {// 如果 head2 为空，不需要做任何操作return;}struct ListNode* tail1 = findTail(*head1); // 找到 head1 的尾节点struct ListNode* tail2 = findTail(head2); // 找到 head2 的尾节点// 将 head1 的尾节点指向 head2 的头节点tail1->next = head2;// 将 head2 的尾节点指向 head1 的头节点tail2->next = *head1;
}// 打印单向循环链表
void printList(struct ListNode* head) {if (head == NULL) return;struct ListNode* current = head;do {printf("%d -> ", current->val);current = current->next;} while (current != head);printf("(回到头部)\n");
}// 主函数示例
int main() {// 创建链表 head1: 1 -> 2 -> 3 -> 1struct ListNode* head1 = createNode(1);head1->next = createNode(2);head1->next->next = createNode(3);head1->next->next->next = head1; // 形成循环// 创建链表 head2: 4 -> 5 -> 6 -> 4struct ListNode* head2 = createNode(4);head2->next = createNode(5);head2->next->next = createNode(6);head2->next->next->next = head2; // 形成循环printf("连接前:\n");printf("链表 head1: ");printList(head1);printf("链表 head2: ");printList(head2);// 连接两个链表connectLists(&head1, head2);printf("连接后:\n");printf("链表 head1: ");printList(head1);// 清理内存（由于循环链表会形成无限循环，清理内存会更加复杂，这里省略清理部分）return 0; // 返回成功
}

5