文章目录

题一：反转链表
- 法1：指针反向
- 法2：指针翻转
- 法3：头插法
题二：链表的中间节点
- 法1：统计节点减半法
- 法2：快慢指针法
题三：合并两个有序链表
- 法1：tail拼接法
- 法2：哨兵位法
题四：环形链表
- 错误示范：
- 方法：快慢指针法
- 拓展面试题：
- - 1小题：slow一次走1步，fast一次走2步
  - 2小题：
  - - 2.1：slow一次走1步，fast一次走3步
    - - N为2的倍数（偶数）：
      - N不是2的倍数（奇数）：
      - C-1为2的倍数：
        C-1不是2的倍数：
    - 2.2：slow一次走1步，fast一次走4步
  - 总结
题五：环形链表II
- 结论
- 证明
- - 分析：
  - 情况1：环大头短
  - - - 1、fast走一圈及以下（错误示范）：
      - 2、fast走大于等于一圈不到两圈：
  - 情况2：环小头长
  - 展示证明：
  - - 1、总结：L+N * C+X >= C，N>=1
    - 2、C <= L+N * C+X < 2C，N=1
    - 3、L+N * C+X >= 2C，N >= 2
感受

题一：反转链表

链接：
LeetCode206.反转链表

法1：指针反向

说明：将指针的方向反向，在原链表的头前加上NULL

//法一：指针反向
struct ListNode* reverseList(struct ListNode* head)
{//1、原链表为：[]if(head == NULL){return NULL;}//2、原链表只有一个节点else if(head->next == NULL){return head;}//注意点1：这前两步可以合并，直接return head;//3、有两个及以上节点else{struct ListNode* prev = head;struct ListNode* next = head->next;struct ListNode* flag = next->next;//注意点2：原链表的头变成新链表的尾，尾->next = NULLprev->next = NULL;//注意点3：退出while时：flag=NULL, next是原链表最后一个节点，但还没连接在新链表上while(flag! = NULL || next->next! = NULL){next->next = prev;prev = next;next = flag;//注意点4：用标记指针找下一位flag = flag->next;}//注意点5：连接原链表尾节点到新链表next->next = prev;//注意点6：退出循环后flag=NULL，next指向最后一个节点return next;}
}

法2：指针翻转

说明：以每个节点为中心将指针全部翻转，在原链表的头前面加上NULL

//法二：指针翻转
struct ListNode* reverseList(struct ListNode* head)
{//1、原链表为：[]if(head == NULL){return NULL;}//2、原链表有一个及以上节点//注意点1：next和flag前面也加*，否则这两个就变成结构体，而不是结构体指针struct ListNode* prev = NULL, *next = head, *flag = next->next;//注意点2：退出循环时，next=NULL，flag=NULL//且法二比法一多执行一次循环，最后一个节点已经接入新链表while(next!=NULL){//注意点3：第一次执行时prev=NULL，所以已经将原链表的头改为新链表的尾next->next = prev;prev = next;next = flag;//注意点4：记录原链表下一位，if(flag!=NULL){flag=flag->next;}}//注意点5：退出循环后，next=NULL,prev指向最后一个节点return prev;
}

法3：头插法

说明：用newhead去拼接，把原链表节点一个一个拿出来插在newhead前面

//法二：头插法
struct ListNode* reverseList(struct ListNode* head)
{//注意点1：这里的newHead相当于法二中的prev, cur相当于next, next相当于flagstruct ListNode* newHead = NULL;struct ListNode* cur = head;//注意点2：退出循环后cur=NULL, 和指针翻转相似while(cur!=NULL){//注意点3：next和while里的条件对应struct ListNode* next = cur->next;cur->next = newHead;newHead = cur;cur = next;}//注意点4：退出循环后，cur=NULL,newHead是原链表最后一个节点,且已经连接到新链表return newHead;
}

说明：

这三个方法共性：
1、都有三个指针
2、第一第二个指针操作链表的指向
3、第三个指针记录原链表向后找

题二：链表的中间节点

链接：
LeetCode876.链表的中间节点

法1：统计节点减半法

//法一：统计节点减半法
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* cur = head;//1、统计节点个数int count = 1;while(cur->next!=NULL){cur=cur->next;count++;}//2、查找中间节点count /= 2;cur = head;while(count>0){cur=cur->next;count--;}//3、返回中间节点return cur;
}

法2：快慢指针法

说明：用快慢指针遍历一遍，slow指针即为中间节点。
规则：fast=slow=head，fast每次走两个节点，slow每次走一个节点，当走到末尾时，slow刚好走到一半

//法二：快慢指针法(只遍历一遍链表)
//fast每次走两个节点，slow每次走一个
//1、当fast走到尾节点表示奇数个节点 2、当fast走到NULL表示偶数个节点
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fast = head, *slow = head;//注意1：while里面的两个条件不能交换，否则出错。//因为要先判断fast位置是否等于NULLwhile(fast!=NULL && fast->next!=NULL){fast=fast->next->next;slow=slow->next;}//注意2：退出循环fast=NULL表示偶数个，fast->next=NULL表示奇数个return slow;
}

题三：合并两个有序链表

链接：
LeetCode21.合并两个有序链表

法1：tail拼接法

说明：用head和tail重新去拼接
规则：list1和list2找小尾插到tail后面，最后返回记录的head。
两种写法的方法一样，但相对来说第二种写法更容易理解

第一种写法：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{//1、list2 != NULL || 二者都为NULLif(list1 == NULL){return list2;}//2、list1 !=NULL || 二者都为NULLif(list2 ==NULL){return list1;}//3、二者都不为NULLstruct ListNode* head = NULL;struct ListNode* tail = NULL;while(list1!=NULL && list2!=NULL){//注意点1：比较list1和list2的值，小的拿来尾插if(list1->val <= list2->val){//注意点2：处理第一个节点，放入head和tail，记录好头节点if(head==NULL){head = tail = list1;}else{tail->next = list1;tail=tail->next;}//注意3：从list1转移一个节点在head链表上后，//因为这个节点还没有断掉与list1的联系，所以往后找节点list1 = list1->next;}else{if(head==NULL){head = tail = list2;}else{tail->next=list2;tail=tail->next;}list2=list2->next;}}//注意点5：走完循环,list1还有节点if(list1!=NULL){tail->next = list1;}if(list2!=NULL){tail->next = list2;}//注意点6：返回记录的头节点return head;
}

第二种写法：

//简化版
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{//1、list2 != NULL || 二者都为NULLif(list1 == NULL){return list2;}//2、list1 !=NULL || 二者都为NULLif(list2 ==NULL){return list1;}struct ListNode* head = NULL;struct ListNode* tail = NULL;//注意1：提前把head和tail的第一个节点准备好,保证tail!=NULLif(list1->val < list2->val){head=tail=list1;list1=list1->next;}else{head=tail=list2;list2=list2->next;}//3、遍历找小尾插while(list1!=NULL && list2!=NULL){//注意点2：第一次循环是，tail已经有一个头节点if(list1->val < list2->val){tail->next = list1;list1=list1->next;}else{tail->next=list2;list2=list2->next;}//注意点3：tail连接新节点后，要指向这个新节点，便于下次尾插tail=tail->next;}//注意点4：走完循环,list1还有节点if(list1!=NULL){tail->next = list1;}if(list2!=NULL){tail->next = list2;}//4、返回记录的头节点return head;
}

法2：哨兵位法

说明：创建一个哨兵（头节点），然后用这个节点把list1和list2两个链表有序连接
优点：
1、可以不用再考虑法一中，tail连接头节点单独讨论的过程，也便于理解
2、可以解决二级指针传参的问题，如在带头双向循环链表里

//法二：哨兵法
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{//1、list2 != NULL || 二者都为NULLif(list1 == NULL){return list2;}//2、list1 !=NULL || 二者都为NULLif(list2 ==NULL){return list1;}//注意1：提前把哨兵head准备好struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* tail = head;//3、遍历找小尾插while(list1!=NULL && list2!=NULL){//注意点2：第一次循环是，tail已经有一个头节点if(list1->val < list2->val){tail->next = list1;list1=list1->next;}else{tail->next=list2;list2=list2->next;}//注意点3：tail连接新节点后，要指向这个新节点，便于下次尾插tail=tail->next;}//注意点4：走完循环,list1还有节点if(list1!=NULL){tail->next = list1;}if(list2!=NULL){tail->next = list2;}//4、返回存储数据的第一个节点struct ListNode* first = head->next;free(head);head=NULL;return first;
}

题四：环形链表

链接：
LeetCode141.环形链表

错误示范：

根本原因：不知道入环位置
解释：找是不是第一个节点入环，需要从第二个开始找当前节点是否与第一个节点相同
不同就继续找下一个。那就出了一个问题，如果非第一个节点是入环，就陷入了死循环。

bool hasCycle(struct ListNode *head) 
{struct ListNode* cur = head, *mark = head;while(mark!=NULL){//cur!=NULL这个循环会陷入死循环while(cur!=NULL){if(cur->next==mark){return true;}}mark=mark->next;cur=mark;}return false;
}

方法：快慢指针法

说明：快指针fast一次走两个节点，慢指针slow一次走一个节点。fast先进入环，slow后进入环，然后fast在环中追逐slow，直到fast=slow时return true。

//快慢指针
bool hasCycle(struct ListNode *head) 
{//1、有环：快指针先进入环，然后慢指针进入环，最后fast追逐slow直到相等时停止struct ListNode *fast = head, *slow = head;while(fast!=NULL && fast->next!=NULL){fast=fast->next->next;slow=slow->next;if(fast==slow){return true;}}//2、fast=NULL或者fast->next=NULL。表示链表不带环就退出循环，fast=NULL表示偶数个节点，fast->next=NULL表示奇数个节点return false;
}

拓展面试题：

题目：

slow一次走1步，fast一次走2步。请证明slow和fast一定在环内相遇，即fast一定追到slow？有没有追不上的可能？
slow一次走1步，fast一次走3步行吗？
slow一次走1步，fast一次走4步呢？
slow一次走1步，fast一次走n步呢？

1小题：slow一次走1步，fast一次走2步

结论：slow一次走1步，fast一次走2步。在环内fast一定能追到slow，因为步数相差1。

如下图所示：
1、分析题目：

2、画图理解：

2小题：

2.1：slow一次走1步，fast一次走3步

结论：

N是2（3-1）的倍数，一定能相遇，
N不是2的倍数，但fast超过slow时相隔1，所以如果C-1为2的倍数就可以相遇
N不是2的倍数，且C-1不是2的倍数永不相遇

如下图所示：
1、分析题目：
题目分析

2、画图理解

N为2的倍数（偶数）：

fast和slow能相遇，因为3-1=2，fast和slow步数相差2，所以2的倍数就能相遇
N为偶数

N不是2的倍数（奇数）：

设链表节点为C个，C-1为2（3-1）的倍数，则fast和slow能相遇

C-1为2的倍数：

注意：

在这里fast走了两圈即6个N，slow走了2个N，即fast第一圈跳过了slow，因为C-1为偶数，第二圈追了回来。

入环和反超

C-1不是2的倍数：

当N=1时，C=6时：fast第一次反超slow，这时C-1=5不是2的倍数，最终陷入死循环
第一次反超：

后续循环：
在这里插入图片描述

2.2：slow一次走1步，fast一次走4步

结论：

N为3（4-1）的倍数，一定能相遇。
N不是3的倍数，但fast第一次反超slow相隔1时，C-1为3的倍数，就能相遇
N不是3的倍数，但fast第一次反超slow相隔2时，C-2为3的倍数，就能相遇
N不是3的倍数，fast第一次反超slow时C-1或者C-2不是3的倍数，就一定不能相遇，由此可以推广到slow走一步，fast走n步。

总结

slow一次走1步，fast一次走2步：fast一定能追上slow
slow一次走1步，fast一次走3步：fast不一定能追上slow
1、slow入环时二者相距离N为步数差（2）的倍数，则可以追上
2、第一次反超时，相间隔距离为1，环的长度C-1为步数差（2）的倍数，就可以追上。
3、以上两者都不是，则永久循环。
slow一次走1步，fast一次走n步：
与fast走3步相类似。

题五：环形链表II

链接：
LeetCode142.环形链表II

结论

说明：slow一次走1步，fast一次走2步。从fast和slow相遇节点meet开始，和从开头head位置开始，二者到入环的长度相等，即它们会在入环处相遇

//推导出的结论：一个指针从相遇节点往后走，一个指针从head往后走，它们会在入环处相遇
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fast = head, *slow = head;while(fast!=NULL && fast->next!=NULL){fast=fast->next->next;slow=slow->next;//注意点2：fast追上slow, 环中相遇节点meet往后走//start从head位置往后找，meet和start在入环节点处相遇if(fast==slow){struct ListNode *meet = fast;struct ListNode *start = head;while(start!=meet){start=start->next;meet=meet->next;}return start;}}//注意点2：fast能出循环，表示链表没有环形部分return NULL;
}

证明

分析：

规定：设L为head到入环位置的长度，X为slow走的长度(也为fast追slow最后不到一圈的长度)，C为环的长度，N为fast追slow走过完整的圈数，从顺时针看。
meet为slow和fast相遇时的节点。

在这里插入图片描述

情况1：环大头短

说明：环大头短的情况下，fast走的路程是大于等于1圈，小于2圈的且fast路程C <= N*C+X < 2C。这里N=1。

1、fast走一圈及以下（错误示范）：

在这里插入图片描述

注意：环大头短，且fast走一圈以下不能实现，最低都得是满一圈。因为fast在环入口对面到环的范围时，fast已经走了右半环，最后fast走的路程：L+C+X

2、fast走大于等于一圈不到两圈：

在这里插入图片描述

情况2：环小头长

说明：环小头长的情况下，fast走的路程大于等于两圈，且fast路程N*C+X >= 2C，这里N>=2

在这里插入图片描述

展示证明：

1、总结：L+N * C+X >= C，N>=1

在这里插入图片描述

2、C <= L+N * C+X < 2C，N=1

即环大头短，fast路程大于等于一圈小于两圈：
在这里插入图片描述

3、L+N * C+X >= 2C，N >= 2

即环小头大，fast路程大于等于两圈：
在这里插入图片描述

感受

在写这一篇博客之前，没接触过环形链表，也没有多大感受，我也没想过这篇博客我会写的这么曲折，花这么长时间。前面几道OJ题画图之后还是容易解决，环形链表知道原理后代码也比较简单。但环形链表原理的证明也太复杂了吧！写了后感觉全身酸麻，主要是证明时，我还走了弯路，写到后面才绕回来，属实裂开。但万幸最终还是通过拼时间完成，花了两天，累的同时也有一种成就感。让这种让人酸痛的题再多来几道吧，让我多感受感受痛苦的滋味！