【数据结构】链表应用-链表重新排序
重新排序
- 反转链表
- 预期实现
- 思路
- 解题过程
- 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; // 定义一个指针third
while (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; // 头节点的数据域为0
head->next = NULL; // 头节点的指针域为空
return head; // 返回头节点
}
// 初始化节点（带节点数据域参数）
Node *InitListWithElem(ElemType e)
{
Node *node = (Node *)malloc(sizeof(node)); // 为节点分配内存
node->data = e; // 节点的数据域为e
node->next = NULL; // 节点的指针域为空
return node; // 返回节点
}
/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{
Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
p->data = e; // 在新节点的数据域存入数据e
p->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; // 在新节点的数据域存入数据e
tail->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; // 在新节点的数据域存入数据e
newnode->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; // 定义一个指针third
while (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 node
p2 = p1->next;
q2 = q1->next;
// 合并节点
p1->next = q1;
q1->next = p2;
// move node
p1 = 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; // 头节点的数据域为0
head->next = NULL; // 头节点的指针域为空
return head; // 返回头节点
}
// 初始化节点（带节点数据域参数）
Node *InitListWithElem(ElemType e)
{
Node *node = (Node *)malloc(sizeof(node)); // 为节点分配内存
node->data = e; // 节点的数据域为e
node->next = NULL; // 节点的指针域为空
return node; // 返回节点
}
/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{
Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
p->data = e; // 在新节点的数据域存入数据e
p->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; // 在新节点的数据域存入数据e
tail->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; // 在新节点的数据域存入数据e
newnode->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; // 定义一个指针third
while (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;
}
/* 链表重新排序 */