【数据结构】链表应用-链表重新排序

重新排序

反转链表
- 预期实现
- 思路
- 解题过程
- code
- - 力扣代码
  - 核心代码
  - 完整代码
- 总结
删除链表中间节点
- 代码
- 解惑
链表重新排序
- 题目描述
- 解题思路
- 解题过程
- 复杂度
- 代码
- - 力扣代码
  - 完整代码

反转链表

预期实现

在这里插入图片描述

思路

你选用何种方法解题？
我选用了迭代法来反转链表。这是一种经典且高效的方法，通过遍历链表并逐个反转节点的指针方向来实现。

用三个指针，分别指向当前节点，前一个节点，后一个节点，然后进行反转

解题过程

这些方法具体怎么运用？

初始化指针：
prevNode：指向已反转部分的头节点，初始为 NULL。
currentNode：指向当前待反转的节点，初始为 head。
nextNode：临时保存当前节点的下一个节点。
遍历链表：
在每次循环中：
保存当前节点的下一个节点到 nextNode。
将当前节点的 next 指针指向 prevNode，实现反转。
将 prevNode 移动到当前节点。
将 currentNode 移动到 nextNode。
结束条件：
当 currentNode 为 NULL 时，表示链表已遍历完毕，此时 prevNode 指向反转后的新头节点。
返回结果：
将 head 指向 prevNode，并返回 head。

作者：北国无红豆
链接：https://leetcode.cn/problems/UHnkqh/solutions/3062635/fan-zhuan-lian-biao-die-dai-fa-by-chun-s-yg81/
来源：力扣（LeetCode）

在这里插入图片描述

然后改变second指向

在这里插入图片描述

移动三个指针
在这里插入图片描述

再次改变second指向
在这里插入图片描述
在继续同步挪动三个指针

……

直到second指向NULL

在这里插入图片描述

最后加个head
在这里插入图片描述

code

力扣代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){if (head == NULL)return NULL;struct ListNode* prevNode = NULL;struct ListNode* currentNode = head;struct ListNode* nextNode;while(currentNode != NULL){nextNode = currentNode->next;currentNode->next = prevNode;prevNode = currentNode;currentNode = nextNode;}head = prevNode;return head;
}作者：北国无红豆
链接：https://leetcode.cn/problems/UHnkqh/solutions/3062635/fan-zhuan-lian-biao-die-dai-fa-by-chun-s-yg81/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

核心代码

/*** @description: 反转链表* @param {Node} *head  头节点* @return {*}          返回反转后的头节点* note:* 空指针检查:检查head是否为NULL，避免非法访问。* 直接操作原头节点:反转完成后，将原头节点的next指向反转后的首节点（prev），无需新建头节点。* 处理所有边界条件:链表为空（head->next为NULL）时，循环不会执行，直接返回head。** 创建的三个节点是first,second,third 局部指针变量，不需要free释放内存* first->next 或 first->data 是通过指针访问节点的成员。* 直接写 first 表示操作指针本身（例如赋值或比较）。*/
Node *ReverseList(Node *head)
{if (head == NULL){return NULL; // 处理空头节点情况}Node *first = NULL;        // 定义一个指针first，指向空NULL，代表反转之后的尾Node *second = head->next; // 定义一个指针second，指向头节点的下一个节点，代表当前节点Node *third = NULL;        // 定义一个指针thirdwhile (second != NULL){third = second->next; // 将third指向second的下一个节点，保存下一个节点的地址second->next = first; // 将当前节点的next指针指向first，实现反转first = second;       // 将first指向second，移动到下一个节点，指针的赋值操作second = third;       // 将second指向third，移动到下一个节点}head->next = first; // 头节点的next指针指向first，实现反转return head; // 返回新的头节点
}int main(int argc, char const *argv[])
{// 初始化链表Node *list = InitList();// 获取尾节点Node *tail = GetTail(list);tail = InsertTail(tail, 1);tail = InsertTail(tail, 2);tail = InsertTail(tail, 3);tail = InsertTail(tail, 4);tail = InsertTail(tail, 5);tail = InsertTail(tail, 6);TraverseList(list); // 遍历链表// 反转链表Node *ReverseListHead = ReverseList(list);TraverseList(ReverseListHead); // 遍历链表return 0;
}

完整代码

/*** @description: 反转链表** 思路：用三个指针，分别指向当前节点，前一个节点，后一个节点，然后进行反转*/#include <stdio.h>
#include <stdlib.h>typedef int ElemType; // 定义元素类型typedef struct node // 定义节点类型
{ElemType data;struct node *next;
} Node;/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存head->data = 0;                            // 头节点的数据域为0head->next = NULL;                         // 头节点的指针域为空return head;                               // 返回头节点
}// 初始化节点（带节点数据域参数）
Node *InitListWithElem(ElemType e)
{Node *node = (Node *)malloc(sizeof(node)); // 为节点分配内存node->data = e;                            // 节点的数据域为enode->next = NULL;                         // 节点的指针域为空return node;                               // 返回节点
}/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据ep->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)L->next = p;                            // 头节点的指针域指向新节点return 1;                               // 返回1表示成功
}
/* 单链表 - 遍历 */
void TraverseList(Node *L)
{Node *p = L->next; // 从头节点的下一个节点开始遍历while (p != NULL)  // 遍历到链表末尾{printf("%d ", p->data); // 输出节点的数据域,这里是%d,因为ElemType是int类型p = p->next;            // 移动到下一个节点}printf("\n"); // 换行
}/* 单链表 - 尾插法 */
// 获取尾节点地址
Node *GetTail(Node *List)
{Node *p = List;         // 从头节点开始遍历while (p->next != NULL) // 遍历到链表末尾{p = p->next; // 移动到下一个节点}return p; // 返回尾节点
}/*** @Description:单链表 - 尾插法插入数据* @param {Node} *tail   尾节点* @param {ElemType} e   插入的数据* @return {*}           返回新的尾节点*/
Node *InsertTail(Node *tail, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据etail->next = p;                         // 尾节点的指针域指向新节点p->next = NULL;                         // 新节点的指针域为空return p;                               // 返回新的尾节点
}/*** @Description:单链表 - 在链表尾部插入节点* @param {Node} *tail   链表尾部节点* @param {Node} *node   要插入的节点* @return {Node *}      插入节点后的链表尾部节点*/
Node *InsertTailWithNode(Node *tail, Node *node)
{tail->next = node; // 尾节点的指针域指向要插入的节点node->next = NULL; // 要插入的节点的指针域为空return node;       // 返回新的尾节点
}/*** @Description:单链表 - 在指定位置插入数据* @param {Node} *L     单链表的头节点* @param {int} pos     位置* @param {ElemType} e  插入的数据* @return {*}*/
int InsertPosNode(Node *L, int pos, ElemType e)
{// 用来保存插入位置的前驱节点Node *p = L; // 从头节点开始遍历int i = 0;// 遍历链表-找到插入位置的前驱节点while (i < pos - 1) // 遍历到插入位置的前驱节点{p = p->next; // 移动到下一个节点i++;if (p == NULL) // 判断是否到达链表末尾{printf("插入位置不合法\n");return 0;}}Node *newnode = (Node *)malloc(sizeof(Node)); // 创建一个新的节点newnode->data = e;                            // 在新节点的数据域存入数据enewnode->next = p->next;                      // 新节点的指针域指向插入位置的前驱节点的下一个节点p->next = newnode;                            // 插入位置的前驱节点的指针域指向新节点return 1;
}/*** @Description:单链表 - 删除指定位置的节点* @param {Node} *L 单链表的头节点* @param {int} pos 位置* @return {*}       返回1表示成功*/
int DeletePosNode(Node *L, int pos)
{// 用来保存删除位置的前驱节点Node *p = L; // 从头节点开始遍历int i = 0;// 遍历链表-找到删除节点的前驱节点while (i < pos - 1) // 遍历到删除位置的前驱节点{p = p->next; // 移动到下一个节点i++;if (p == NULL) // 判断是否到达链表末尾{printf("删除位置不合法\n");return 0;}}if (p->next == NULL) // 判断删除位置是否合法{printf("删除位置不合法\n");return 0;}Node *q = p->next; // 保存要删除的节点的地址p->next = q->next; // 删除节点的前驱节点的指针域 指向 删除节点的下一个节点free(q);           // 释放删除节点的内存return 1; // 返回1表示成功
}int GetListLength(Node *L)
{int length = 0;Node *p = L; // 从头节点开始遍历,头节点算在内while (p != NULL){p = p->next;length++;}return length;
}void FreeList(Node *L)
{Node *p = L->next; // 从头节点的下一个节点开始遍历,头节点不需要释放Node *q = NULL;    // 用来保存下一个节点的地址,q能掌握下一个节点的地址，这是灵魂所在while (p != NULL){q = p->next; // 保存下一个节点的地址free(p);     // 释放当前节点的内存p = q;       // 移动到下一个节点}L->next = NULL; // 头节点的指针域为空
}// 查找倒数第k个节点
int findNodeFS(Node *L, int k)
{Node *fast = L->next;Node *slow = L->next;for (int i = 0; i < k; i++){fast = fast->next;}while (fast != NULL){fast = fast->next;slow = slow->next;}printf("倒数第%d个节点值为：%d\n", k, slow->data);return 1;
}// 查找两个节点共同后缀的起始位置
Node *findIntersectionNode(Node *headA, Node *headB)
{if (headA == NULL || headB == NULL){return NULL;}Node *p = headA;int lenA = 0;int lenB = 0;// 遍历链表A，获取链表A的长度while (p != NULL){p = p->next;lenA++;}// 遍历链表B，获取链表B的长度p = headB;while (p != NULL){p = p->next;lenB++;}Node *fast; // 快指针Node *slow; // 慢指针int step;   // 两个单词之间数量的差值，可以用于快指针先走的步数if (lenA > lenB){step = lenA - lenB;fast = headA;slow = headB;}else{step = lenB - lenA;fast = headB;slow = headA;}// 让快指针先走step步for (int i = 0; i < step; i++){fast = fast->next;}// 快慢指针同步走，直到指向同一个节点退出循环while (fast != slow){fast = fast->next;slow = slow->next;}return fast;
}// 函数：RemoveEqualNodes
// 功能：删除链表中与给定值相等的节点
// 参数：Node *L：链表头指针，int n：链表的长度
// 返回值：无
void RemoveEqualNodes(Node *L, int n)
{// TODO: 实现删除链表中与给定值相等的节点的功能Node *p = L;                                   // 定义一个指针p，指向链表的头节点int index;                                     // 定义一个变量index，作为数组下标使用int *q = (int *)malloc(sizeof(int) * (n + 1)); // 在堆内存中分配一个数组，用来存储已经出现过的绝对值/* 遍历数组，初始化为0 */for (int i = 0; i < n + 1; i++){*(q + i) = 0; // 初始化为0，表示没有出现过这个绝对值}while (p->next != NULL){// 获取绝对值index = abs(p->next->data); // 计算当前节点的绝对值，作为数组下标使用if (*(q + index) == 0) // 如果这个绝对值没有出现过{*(q + index) = 1; // 标记为已经出现过p = p->next;      // 移动到下一个节点}else // 如果这个绝对值已经出现过,删除当前节点{Node *tempNode = p->next; // 保存要删除的节点的地址p->next = tempNode->next; // 删除当前节点free(tempNode);           // 释放当前节点的内存}}free(q); // 释放数组的内存
}/*** @description: 反转链表* @param {Node} *head  头节点* @return {*}          返回反转后的头节点* note:* 空指针检查:检查head是否为NULL，避免非法访问。* 直接操作原头节点:反转完成后，将原头节点的next指向反转后的首节点（prev），无需新建头节点。* 处理所有边界条件:链表为空（head->next为NULL）时，循环不会执行，直接返回head。** 创建的三个节点是first,second,third 局部指针变量，不需要free释放内存* first->next 或 first->data 是通过指针访问节点的成员。* 直接写 first 表示操作指针本身（例如赋值或比较）。*/
Node *ReverseList(Node *head)
{if (head == NULL){return NULL; // 处理空头节点情况}Node *first = NULL;        // 定义一个指针first，指向空NULL，代表反转之后的尾Node *second = head->next; // 定义一个指针second，指向头节点的下一个节点，代表当前节点Node *third = NULL;        // 定义一个指针thirdwhile (second != NULL){third = second->next; // 将third指向second的下一个节点，保存下一个节点的地址second->next = first; // 将当前节点的next指针指向first，实现反转first = second;       // 将first指向second，移动到下一个节点，指针的赋值操作second = third;       // 将second指向third，移动到下一个节点}head->next = first; // 头节点的next指针指向first，实现反转return head; // 返回新的头节点
}int main(int argc, char const *argv[])
{// 初始化链表Node *list = InitList();// 获取尾节点Node *tail = GetTail(list);tail = InsertTail(tail, 1);tail = InsertTail(tail, 2);tail = InsertTail(tail, 3);tail = InsertTail(tail, 4);tail = InsertTail(tail, 5);tail = InsertTail(tail, 6);TraverseList(list); // 遍历链表// 反转链表Node *ReverseListHead = ReverseList(list);TraverseList(ReverseListHead); // 遍历链表return 0;
}

总结

方法：迭代法，通过遍历链表逐个反转节点指针。
时间复杂度：O(n)，只需遍历链表一次。
空间复杂度：O(1)，仅使用常数个额外指针。
优点：高效、直观，适合所有单链表反转场景。

删除链表中间节点

在这里插入图片描述

删除节点4
使用快慢指针，快指针每次走两步，慢指针每次走一步，当快指针走到链表末尾时，慢指针指向的就是链表中间节点。
如果链表长度为偶数，中间节点有两个，通常删除第二个中间节点。

在这里插入图片描述

代码

int DeleteMidNode(Node *head)
{Node *fastNode = head->next; // 快指针,先走一步，后面每次走两步Node *slowNode = head;       // 慢指针,每次走一步/* 当快指针的下一个或者下一个的下一个是NULL，说明快指针已经走到了链表的末尾 */while (fastNode != NULL && fastNode->next != NULL) // 快指针走到链表末尾时，慢指针指向的就是链表中间节点{fastNode = fastNode->next->next; // 快指针每次走两步slowNode = slowNode->next;       // 慢指针每次走一步}// 删除中间节点Node *tempNode = slowNode->next; // 保存要删除的节点的地址slowNode->next = tempNode->next; // 删除当前节点free(tempNode);                  // free(tempNode) 释放的是 tempNode 所指向的内存，也就是被删除节点的堆内存return 1;                        // 删除成功返回1
}

解惑

notes:问题：我自己创建了一个tempNode，然后free了tempNode，那么被删除的那个节点，没有被free，那么在内存里还存在被删除的节点吗？下面是deepseek的回答：
tempNode 的作用：tempNode 是一个指针，它指向的是 slowNode->next，也就是链表中要被删除的节点。tempNode 本身只是一个指针变量，它存储的是被删除节点的内存地址。
free(tempNode) 的作用：free(tempNode) 释放的是 tempNode 所指向的内存，也就是被删除节点的内存。free 并不会释放 tempNode 这个指针变量本身（指针变量是存储在栈上的），而是释放指针所指向的堆内存。
被删除节点的内存状态：当你调用 free(tempNode) 后，被删除节点的内存会被操作系统标记为“可回收”，这意味着这块内存不再属于你的程序，操作系统可以将其重新分配给其他部分使用。因此，被删除的节点在内存中不再有效。
总结：tempNode 会随着函数结束自动销毁；被删除的节点是通过 free 函数释放的内存。

链表重新排序

题目描述

在这里插入图片描述

解题思路

预期效果
在这里插入图片描述

从中间位置断开（找到链表的中间节点：使用快慢指针法，快指针每次走两步，慢指针每次走一步，当快指针到达链表末尾时，慢指针正好在链表的中间位置。）
反转后面的链表，456变成654（反转后半部分链表：从中间节点开始，反转链表的后半部分）
见缝插针，缝合链表（合并两个链表：将前半部分链表和反转后的后半部分链表交替合并）

解题过程

这些方法具体怎么运用？

快慢指针找中间节点：
初始化快指针 fastNode 和慢指针 slowNode 都指向链表的头节点 head。
快指针每次移动两步，慢指针每次移动一步，直到快指针到达链表末尾。
当快指针到达末尾时，慢指针正好在链表的中间位置。
反转链表：
从慢指针 slowNode 的下一个节点开始，反转链表的后半部分。
使用三个指针 prevNode、currentNode 和 nextNode 来反转链表。
反转完成后，将前半部分链表和后半部分链表断开。
合并链表：
使用两个指针 p1 和 q1 分别指向前半部分链表和反转后的后半部分链表的头节点。
交替合并两个链表，直到其中一个链表遍历完毕。

作者：北国无红豆
链接：https://leetcode.cn/problems/LGjMqU/solutions/3063709/zhong-pai-lian-biao-kuai-man-zhi-zhen-fa-aghl/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度

时间复杂度: O(n)
空间复杂度: O(1)

代码

力扣代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/void reorderList(struct ListNode* head){/* 1.快慢指针找中间节点 */struct ListNode *fastNode = head;struct ListNode *slowNode = head;while((fastNode != NULL) && (fastNode->next != NULL)){fastNode = fastNode->next->next;slowNode = slowNode->next;}/* 2.反转链表 - 三指针 */struct ListNode *prevNode = NULL;struct ListNode *currentNode = slowNode->next;struct ListNode *nextNode = NULL;slowNode->next = NULL;  // 断开前后链表while( currentNode != NULL ){nextNode = currentNode->next;currentNode->next = prevNode;prevNode = currentNode;currentNode = nextNode;}/* 3.合并链表 */struct ListNode *p1 = head;struct ListNode *q1 = prevNode;struct ListNode *p2, *q2;while((p1!=NULL) && (q1!=NULL)){// save next nodep2 = p1->next;q2 = q1->next;// 合并节点p1->next = q1;q1->next = p2;// move nodep1 = p2;q1 = q2;}
}

完整代码

/*** @description: 删除链表中间节点* 思路：快慢指针，快指针每次走两步，慢指针每次走一步，当快指针走到链表末尾时，慢指针指向的就是链表中间节点。*/#include <stdio.h>
#include <stdlib.h>typedef int ElemType; // 定义元素类型typedef struct node // 定义节点类型
{ElemType data;struct node *next;
} Node;/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存head->data = 0;                            // 头节点的数据域为0head->next = NULL;                         // 头节点的指针域为空return head;                               // 返回头节点
}// 初始化节点（带节点数据域参数）
Node *InitListWithElem(ElemType e)
{Node *node = (Node *)malloc(sizeof(node)); // 为节点分配内存node->data = e;                            // 节点的数据域为enode->next = NULL;                         // 节点的指针域为空return node;                               // 返回节点
}/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据ep->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)L->next = p;                            // 头节点的指针域指向新节点return 1;                               // 返回1表示成功
}
/* 单链表 - 遍历 */
void TraverseList(Node *L)
{Node *p = L->next; // 从头节点的下一个节点开始遍历while (p != NULL)  // 遍历到链表末尾{printf("%d ", p->data); // 输出节点的数据域,这里是%d,因为ElemType是int类型p = p->next;            // 移动到下一个节点}printf("\n"); // 换行
}/* 单链表 - 尾插法 */
// 获取尾节点地址
Node *GetTail(Node *List)
{Node *p = List;         // 从头节点开始遍历while (p->next != NULL) // 遍历到链表末尾{p = p->next; // 移动到下一个节点}return p; // 返回尾节点
}/*** @Description:单链表 - 尾插法插入数据* @param {Node} *tail   尾节点* @param {ElemType} e   插入的数据* @return {*}           返回新的尾节点*/
Node *InsertTail(Node *tail, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据etail->next = p;                         // 尾节点的指针域指向新节点p->next = NULL;                         // 新节点的指针域为空return p;                               // 返回新的尾节点
}/*** @Description:单链表 - 在链表尾部插入节点* @param {Node} *tail   链表尾部节点* @param {Node} *node   要插入的节点* @return {Node *}      插入节点后的链表尾部节点*/
Node *InsertTailWithNode(Node *tail, Node *node)
{tail->next = node; // 尾节点的指针域指向要插入的节点node->next = NULL; // 要插入的节点的指针域为空return node;       // 返回新的尾节点
}/*** @Description:单链表 - 在指定位置插入数据* @param {Node} *L     单链表的头节点* @param {int} pos     位置* @param {ElemType} e  插入的数据* @return {*}*/
int InsertPosNode(Node *L, int pos, ElemType e)
{// 用来保存插入位置的前驱节点Node *p = L; // 从头节点开始遍历int i = 0;// 遍历链表-找到插入位置的前驱节点while (i < pos - 1) // 遍历到插入位置的前驱节点{p = p->next; // 移动到下一个节点i++;if (p == NULL) // 判断是否到达链表末尾{printf("插入位置不合法\n");return 0;}}Node *newnode = (Node *)malloc(sizeof(Node)); // 创建一个新的节点newnode->data = e;                            // 在新节点的数据域存入数据enewnode->next = p->next;                      // 新节点的指针域指向插入位置的前驱节点的下一个节点p->next = newnode;                            // 插入位置的前驱节点的指针域指向新节点return 1;
}/*** @Description:单链表 - 删除指定位置的节点* @param {Node} *L 单链表的头节点* @param {int} pos 位置* @return {*}       返回1表示成功*/
int DeletePosNode(Node *L, int pos)
{// 用来保存删除位置的前驱节点Node *p = L; // 从头节点开始遍历int i = 0;// 遍历链表-找到删除节点的前驱节点while (i < pos - 1) // 遍历到删除位置的前驱节点{p = p->next; // 移动到下一个节点i++;if (p == NULL) // 判断是否到达链表末尾{printf("删除位置不合法\n");return 0;}}if (p->next == NULL) // 判断删除位置是否合法{printf("删除位置不合法\n");return 0;}Node *q = p->next; // 保存要删除的节点的地址p->next = q->next; // 删除节点的前驱节点的指针域 指向 删除节点的下一个节点free(q);           // 释放删除节点的内存return 1; // 返回1表示成功
}int GetListLength(Node *L)
{int length = 0;Node *p = L; // 从头节点开始遍历,头节点算在内while (p != NULL){p = p->next;length++;}return length;
}void FreeList(Node *L)
{Node *p = L->next; // 从头节点的下一个节点开始遍历,头节点不需要释放Node *q = NULL;    // 用来保存下一个节点的地址,q能掌握下一个节点的地址，这是灵魂所在while (p != NULL){q = p->next; // 保存下一个节点的地址free(p);     // 释放当前节点的内存p = q;       // 移动到下一个节点}L->next = NULL; // 头节点的指针域为空
}// 查找倒数第k个节点
int findNodeFS(Node *L, int k)
{Node *fast = L->next;Node *slow = L->next;for (int i = 0; i < k; i++){fast = fast->next;}while (fast != NULL){fast = fast->next;slow = slow->next;}printf("倒数第%d个节点值为：%d\n", k, slow->data);return 1;
}// 查找两个节点共同后缀的起始位置
Node *findIntersectionNode(Node *headA, Node *headB)
{if (headA == NULL || headB == NULL){return NULL;}Node *p = headA;int lenA = 0;int lenB = 0;// 遍历链表A，获取链表A的长度while (p != NULL){p = p->next;lenA++;}// 遍历链表B，获取链表B的长度p = headB;while (p != NULL){p = p->next;lenB++;}Node *fast; // 快指针Node *slow; // 慢指针int step;   // 两个单词之间数量的差值，可以用于快指针先走的步数if (lenA > lenB){step = lenA - lenB;fast = headA;slow = headB;}else{step = lenB - lenA;fast = headB;slow = headA;}// 让快指针先走step步for (int i = 0; i < step; i++){fast = fast->next;}// 快慢指针同步走，直到指向同一个节点退出循环while (fast != slow){fast = fast->next;slow = slow->next;}return fast;
}// 函数：RemoveEqualNodes
// 功能：删除链表中与给定值相等的节点
// 参数：Node *L：链表头指针，int n：链表的长度
// 返回值：无
void RemoveEqualNodes(Node *L, int n)
{// TODO: 实现删除链表中与给定值相等的节点的功能Node *p = L;                                   // 定义一个指针p，指向链表的头节点int index;                                     // 定义一个变量index，作为数组下标使用int *q = (int *)malloc(sizeof(int) * (n + 1)); // 在堆内存中分配一个数组，用来存储已经出现过的绝对值/* 遍历数组，初始化为0 */for (int i = 0; i < n + 1; i++){*(q + i) = 0; // 初始化为0，表示没有出现过这个绝对值}while (p->next != NULL){// 获取绝对值index = abs(p->next->data); // 计算当前节点的绝对值，作为数组下标使用if (*(q + index) == 0) // 如果这个绝对值没有出现过{*(q + index) = 1; // 标记为已经出现过p = p->next;      // 移动到下一个节点}else // 如果这个绝对值已经出现过,删除当前节点{Node *tempNode = p->next; // 保存要删除的节点的地址p->next = tempNode->next; // 删除当前节点free(tempNode);           // 释放当前节点的内存}}free(q); // 释放数组的内存
}/*** @description: 反转链表* @param {Node} *head  头节点* @return {*}          返回反转后的头节点* note:* 空指针检查:检查head是否为NULL，避免非法访问。* 直接操作原头节点:反转完成后，将原头节点的next指向反转后的首节点（prev），无需新建头节点。* 处理所有边界条件:链表为空（head->next为NULL）时，循环不会执行，直接返回head。** 创建的三个节点是first,second,third 局部指针变量，不需要free释放内存* first->next 或 first->data 是通过指针访问节点的成员。* 直接写 first 表示操作指针本身（例如赋值或比较）。*/
Node *ReverseList(Node *head)
{if (head == NULL){return NULL; // 处理空头节点情况}Node *first = NULL;        // 定义一个指针first，指向空NULL，代表反转之后的尾Node *second = head->next; // 定义一个指针second，指向头节点的下一个节点，代表当前节点Node *third = NULL;        // 定义一个指针thirdwhile (second != NULL){third = second->next; // 将third指向second的下一个节点，保存下一个节点的地址second->next = first; // 将当前节点的next指针指向first，实现反转first = second;       // 将first指向second，移动到下一个节点，指针的赋值操作second = third;       // 将second指向third，移动到下一个节点}head->next = first; // 头节点的next指针指向first，实现反转return head; // 返回新的头节点
}int DeleteMidNode(Node *head)
{Node *fastNode = head->next; // 快指针,先走一步，后面每次走两步Node *slowNode = head;       // 慢指针,每次走一步/* 当快指针的下一个或者下一个的下一个是NULL，说明快指针已经走到了链表的末尾 */while (fastNode != NULL && fastNode->next != NULL) // 快指针走到链表末尾时，慢指针指向的就是链表中间节点{fastNode = fastNode->next->next; // 快指针每次走两步slowNode = slowNode->next;       // 慢指针每次走一步}// 删除中间节点Node *tempNode = slowNode->next; // 保存要删除的节点的地址slowNode->next = tempNode->next; // 删除当前节点free(tempNode);                  // free(tempNode) 释放的是 tempNode 所指向的内存，也就是被删除节点的堆内存return 1;                        // 删除成功返回1
}/*** notes:问题：我自己创建了一个tempNode，然后free了tempNode，那么被删除的那个节点，没有被free，那么在内存里还存在被删除的节点吗？下面是deepseek的回答：* tempNode 的作用：tempNode 是一个指针，它指向的是 slowNode->next，也就是链表中要被删除的节点。tempNode 本身只是一个指针变量，它存储的是被删除节点的内存地址。* free(tempNode) 的作用：free(tempNode) 释放的是 tempNode 所指向的内存，也就是被删除节点的内存。free 并不会释放 tempNode 这个指针变量本身（指针变量是存储在栈上的），而是释放指针所指向的堆内存。* 被删除节点的内存状态：当你调用 free(tempNode) 后，被删除节点的内存会被操作系统标记为“可回收”，这意味着这块内存不再属于你的程序，操作系统可以将其重新分配给其他部分使用。因此，被删除的节点在内存中不再有效。** 总结：tempNode 会随着函数结束自动销毁；被删除的节点是通过 free 函数释放的内存。*/// 重新排列链表
void reOrderList(Node *head)
{// TODO: 实现重新排列链表的功能Node *fast = head; // 快指针,不需要从head->next开始，因为要找到中间节点（偶数个节点时，中间节点是中间两个节点的前一个节点,奇数个节点时，中间节点是中间那个节点）Node *slow = head;while (fast != NULL && fast->next != NULL) // 快指针走到链表末尾时，慢指针指向的就是链表中间节点{fast = fast->next->next;slow = slow->next;}Node *first = NULL;        // 用来保存反转后的链表的头节点Node *second = slow->next; // 从中间节点开始反转Node *third = NULL;        // 用来保存下一个节点的地址slow->next = NULL;         // 中间节点的next指向NULL，从中间断开链表，分成两个链表，再合并两个链表while (second != NULL){third = second->next; // 保存下一个节点的地址second->next = first; // 反转first = second;       // 移动到下一个节点second = third;       // 移动到下一个节点}// 合并两个链表Node *p1 = head->next; // 从头节点的下一个节点开始遍历Node *q1 = first;      // 从反转后的链表的头节点开始遍历Node *p2, *q2;while ((p1 != NULL) && (q1 != NULL)) // 当两个链表都没有遍历完时，交替合并两个链表{p2 = p1->next; // 保存p1的下一个节点的地址q2 = q1->next; // 保存q1的下一个节点的地址p1->next = q1; // 交替合并两个链表，p1和q1交替连接，p2和q2交替连接，直到有一个链表遍历完为止q1->next = p2; // 交替合并两个链表，p1和q1交替连接，p2和q2交替连接，直到有一个链表遍历完为止p1 = p2; // 移动到下一个节点q1 = q2; // 移动到下一个节点}
}int main(int argc, char const *argv[])
{// 初始化链表Node *list = InitList();// 获取尾节点Node *tail = GetTail(list);tail = InsertTail(tail, 1);tail = InsertTail(tail, 2);tail = InsertTail(tail, 3);tail = InsertTail(tail, 4);tail = InsertTail(tail, 5);tail = InsertTail(tail, 6);tail = InsertTail(tail, 7);printf("打印链表：\n");TraverseList(list); // 遍历链表printf("重新排列链表：\n");reOrderList(list);  // 重新排列链表TraverseList(list); // 遍历链表return 0;
}/* 链表重新排序 */