【算法日记】链表经典算法（C）：移除元素，反转链表，约瑟夫环问题，找中间节点，分割链表

问题一：删除链表中特定值节点(LC203)

（一）问题描述

给定链表头节点head和整数val，删除所有值等于val的节点，返回新头节点。

示例1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：
输入：head = [], val = 1
输出：[]

示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

（二）解题思路

思路1：遍历数组，值等于val则释放当前节点

思路2：创建新链表，值不等于val则尾插到新链表

（三）代码实现（思路2）

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedefstructListNodeLN;structListNode*removeElements(structListNode*head,intval){LN*newHead=NULL;LN*newTail=NULL;LN*pcur=head;while(pcur){if(pcur->val!=val){//为空if(newHead==NULL){newHead=pcur;newTail=pcur;}else{newTail->next=pcur;newTail=newTail->next;}}pcur=pcur->next;}if(newTail!=NULL)newTail->next=NULL;returnnewHead;}

（四）代码解析

1. 化新链表头尾指针：用newHead记录新链表头节点，newTail维护新链表尾节点，初始均为NULL。
2. 遍历原链表：通过pcur指针遍历输入的原链表head。
3. 筛选保留节点：遇到值不等于val的节点时，若新链表为空（newHead是NULL），该节点同时作为新链表的头和尾；若新链表非空，将该节点链接到新链表尾部，更新newTail。
4. 处理新链表尾节点：遍历结束后，将新链表尾节点的next置为NULL。如果没有这行代码，节点5依旧指向原来指向的节点（也就是节点6），返回的链表就是[1,2,3,4,5,6]
   

问题二：反转链表(LC206)

（一）问题描述

给定链表头节点，反转链表并返回新头节点。

示例1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例2：

输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

（二）解题思路

思路1：创建一个新的链表，依次头插在新链表前
思路2：创建3个指针完成链表翻转

（三）代码实现（思路2）

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedefstructListNodeLN;structListNode*reverseList(structListNode*head){if(head==NULL)returnhead;LN*n1,*n2,*n3;n1=NULL;n2=head;n3=n2->next;while(n2!=NULL){n2->next=n1;n1=n2;n2=n3;if(n3)n3=n3->next;}returnn1;}

（四）代码解析

1. 指针初始化：n1 初始化为 NULL（表示反转后当前节点的前一个节点，初始时没有节点，所以为 NULL ），n2 初始化为 head（从原链表头节点开始处理 ），n3 初始化为 head->next（提前保存当前节点的下一个节点，防止后续指针修改后找不到 ）。
2. 反转循环：在while (n2 != NULL)循环中：
   n2->next = n1; 实现当前节点 n2 指向其前一个节点 n1 ，完成指针反转。
   然后n1 = n2; n2 = n3;让三个指针依次向后移动，准备处理下一个节点。
   if (n3 != NULL)判断下一个节点是否存在，存在则更新n3 = n3->next，保证循环能持续推进。
3. 返回结果：当循环结束时，n2 为 NULL ，此时 n1 指向的就是反转后链表的头节点，返回 n1 。

问题三：合并两个有序链表(LC21)

（一）问题描述

将两个升序链表合并为一个新升序链表返回。

示例1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：
输入：l1 = [], l2 = []
输出：[]

示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

（二）解题思路

• 创建新链表，遍历原来两个链表，将较小值尾插到新链表
• 遍历结果只有两种：l1为空或者l2为空
• 把不为空的l1或l2尾插到新链表

（三）代码实现

typedefstructListNodeLN;structListNode*mergeTwoLists(structListNode*list1,structListNode*list2){LN*l1=list1;LN*l2=list2;if(l1==NULL)returnl2;if(l2==NULL)returnl1;LN*newHead=NULL;LN*newTail=NULL;while(l1&&l2){if(l1->val<l2->val){if(newHead==NULL){newHead=newTail=l1;}else{newTail->next=l1;newTail=newTail->next;}l1=l1->next;}else{if(newHead==NULL){newHead=newTail=l2;}else{newTail->next=l2;newTail=newTail->next;}l2=l2->next;}}if(l1){newTail->next=l1;}if(l2){newTail->next=l2;}returnnewHead;}

优化后：

typedefstructListNodeLN;structListNode*mergeTwoLists(structListNode*list1,structListNode*list2){LN*l1=list1;LN*l2=list2;if(l1==NULL)returnl2;if(l2==NULL)returnl1;LN*newHead=NULL;LN*newTail=NULL;newHead=newTail=(LN*)malloc(sizeof(LN));while(l1&&l2){if(l1->val<l2->val){newTail->next=l1;newTail=newTail->next;l1=l1->next;}else{newTail->next=l2;newTail=newTail->next;l2=l2->next;}}if(l1){newTail->next=l1;}if(l2){newTail->next=l2;}LN*ret=newHead->next;free(newHead);newHead=NULL;returnret;}

注意：动态开辟的内存要手动释放

问题四：找链表中间节点(LC876)

（一）问题描述

找到单链表中间节点，若有两个中间节点，返回第二个。

示例1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例2:

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

（二）解题思路

思路1：计数器遍历链表，得到总数，再遍历一半找到中间节点
思路2：快指针fast每次走两步，慢指针slow每次走一步。当fast走到末尾，slow指向中间节点。

（三）代码实现

ListNode*middleNode(ListNode*head){ListNode*slow=head;ListNode*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}returnslow;}

注意：

• 奇数个节点：fast走到最后，恰好slow走到中间节点
• 偶数个节点：fast就需要走到空，slow走到第二个中间节点

因此循环条件：fast && fast->next顺序不可以更改，因为&&存在逻辑短路，当fast为空就不会对fast解引用访问

问题五：链表分割（按值分区）(面试题02.04)

（一）问题描述

给定链表头节点和特定值x，使所有小于x的节点在大于等于x节点之前，无需保留原相对位置。

示例1:

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：
输入：head = [2,1], x = 2
输出：[1,2]

（二）解题思路

• 思路1:在原链表上进行修改,
  • 若pcur值小于x,往后走
  • 若大于或等于x,尾插在链表后,删除旧节点
• 思路2:创建新链表,遍历原链表
  • 若pcur值小于x,则头插在新链表中
  • 若大于或等于x,尾插在链表后
• 思路3:创建小链表和大链表
  • 若pcur小于x值尾插小链表
  • 大于或等于x值尾插在大链表
  • 小链表尾节点和大链表头节点相连

（三）代码实现(思路3)

typedefstructListNodeLN;structListNode*partition(structListNode*head,intx){if(head==NULL)returnNULL;LN*lessHead,*lessTail,*greaterHead,*greaterTail;lessHead=lessTail=(LN*)malloc(sizeof(LN));greaterHead=greaterTail=(LN*)malloc(sizeof(LN));LN*pcur=head;while(pcur){if(pcur->val<x){lessTail->next=pcur;lessTail=lessTail->next;}else{greaterTail->next=pcur;greaterTail=greaterTail->next;}pcur=pcur->next;}//把尾节点下一个节点置为空,如果不写这行代码会出现死循环(5->2)greaterTail->next=NULL;//两个链表相连lessTail->next=greaterHead->next;LN*tmp=lessHead->next;free(lessHead);lessHead=NULL;free(greaterHead);greaterHead=NULL;returntmp;}

问题六：约瑟夫环问题

（一）问题描述

n个人围成圈，从第1人开始报数，报到m的人离开，最后留下的人编号是多少。

著名的Josephus问题
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与
Josephus及他的朋友躲到⼀个洞中，39个犹太人决定宁愿死也不要被人抓到，于是决定了一个自杀方式，41个人排成⼀个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡。
然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与⾃⼰安排在第16个与第31个位置，于是逃过了这场死亡游戏。

示例1
输入：5,2
返回值：3
说明：开始5个人 1，2，3，4，5 ，从1开始报数，1->1，2->2编号为2的人离开
1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开
1，3，5，从5开始报数，5->1，1->2编号为1的人离开
3，5，从3开始报数，3->1，5->2编号为5的人离开
最后留下人的编号是3

示例2
输入：1,1
返回值：1

（二）解题思路

1. 根据n创建带环链表
2. 遍历带环链表,计数器来模拟报数

（三）代码实现

typedefstructListNodeLN;LN*buyListNode(intval){LN*newNode=(LN*)malloc(sizeof(LN));newNode->val=val;returnnewNode;}LN*createCircle(intn){LN*phead=(LN*)malloc(sizeof(LN));LN*ptail=phead;// 初始化头节点值为1phead->val=1;// 创建2到n号节点for(inti=2;i<=n;i++){ptail->next=buyListNode(i);ptail=ptail->next;}// 尾节点指向头节点，形成环ptail->next=phead;returnptail;}intysf(intn,intm){LN*prev=createCircle(n);// prev指向尾节点LN*pcur=prev->next;// pcur指向头节点（第一个人）intcount=1;// 报数计数器// 当只剩一个节点时结束循环while(pcur->next!=pcur){// 当报数到 m时，移除当前节点if(count==m){prev->next=pcur->next;// 跳过当前节点free(pcur);// 释放内存pcur=prev->next;// 移动到下一个节点count=1;// 重置计数器}else{// 未报数到 m，继续移动指针prev=pcur;pcur=pcur->next;count++;}}// 返回最后剩下的节点的值returnpcur->val;}

（四）代码解析

• 使用prev和pcur两个指针追踪当前节点和前一个节点
• count变量记录当前报数
• 当count等于 m 时：
  • 将前一个节点的 next 指向当前节点的 next，实现当前节点的移除
  • 释放被移除节点的内存
  • 重置计数器，继续下一轮报数
• 循环终止条件：当链表中只剩一个节点（pcur->next == pcur）