一、力扣第21题：合并两个有序链表
题目链接：21. 合并两个有序链表 - 力扣（Leetcode）
题目描述：
解法思路
对于这个题目而言，我们肯定是很熟悉的，因为我们已经讲解过一个合并两个有序数组的题目了。这道题完全只是将数组改成了链表。那么我们在链表中使用的方法是尾插法。谁小先插谁
我们先过一遍思路吧，首先我们先看这个图
我们的思路是这样的，先创建两个指针,newHead和tail，用于记录最后返回的链表的头和尾，我们让他们一开始指向NULL
然后我们看如果list1->val<list2->val时，我们就让newHead和tail都指向list1,然后tail向后走一步,list向后走一步，反之则移动执行另外一个链表的操作，如下图所示
然后我们一直循环下去
当只要有一个链表为空以后，那么直接将两个链表链接起来即可
这就是我们的大体思路，但是需要注意的是，有可能一开始会有其中一个链表是空链表，那么这种我们可以一开始做一个判断，只要有一个为空，返回另外一个链表即可
代码一
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ //特殊情况的处理 if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } //定义返回链表的头和尾部 struct ListNode* newHead=NULL; struct ListNode* tail=NULL; //只要两个都不是空链表那么就可以继续执行下去 while(list1 && list2) { //1的值小于2的值时 if(list1->val<list2->val) { //链表头为空，这是第一次插入，需要特殊处理 if(newHead==NULL) { newHead=tail=list1; list1=list1->next; } //正常情况处理 else { tail->next=list1; list1=list1->next; tail=tail->next; } } //1的值大于等于2的值时 else { //链表头为空，是第一次插入，需要特殊处理 if(newHead==NULL) { newHead=tail=list2; list2=list2->next; } //正常情况处理 else { tail->next=list2; tail=tail->next; list2=list2->next; } } } if(list1==NULL) { tail->next=list2; } else { tail->next=list1; } return newHead; }
运行结果为
代码二
其实我们可以将上面的代码进行简化处理，我们可以在循环内只处理尾插，第一个结点放在外面处理
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ //特殊情况的处理 if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } //定义返回链表的头和尾部 struct ListNode* newHead=NULL; struct ListNode* tail=NULL; //处理头节点 if(list1->val < list2->val) { newHead=tail=list1; list1=list1->next; } else { newHead=tail=list2; list2=list2->next; } //只要两个都不是空链表那么就可以继续执行下去 while(list1 && list2) { //1的值小于2的值时 if(list1->val<list2->val) { //尾插 tail->next=list1; list1=list1->next; tail=tail->next; } //1的值大于等于2的值时 else { //尾插 tail->next=list2; tail=tail->next; list2=list2->next; } } if(list1==NULL) { tail->next=list2; } else { tail->next=list1; } return newHead; }
代码三
其实我们还可以使用一个哨兵位来解决第一个头节点的问题
代码如下
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ //特殊情况的处理 if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } //定义返回链表的头和尾部 struct ListNode* newHead=NULL; struct ListNode* tail=NULL; newHead=tail=(struct ListNode*)malloc(sizeof(struct ListNode)); //只要两个都不是空链表那么就可以继续执行下去 while(list1 && list2) { //1的值小于2的值时 if(list1->val<list2->val) { //尾插 tail->next=list1; list1=list1->next; tail=tail->next; } //1的值大于等于2的值时 else { //尾插 tail->next=list2; tail=tail->next; list2=list2->next; } } if(list1==NULL) { tail->next=list2; } else { tail->next=list1; } return newHead->next; }
二、力扣第141题：环形链表
题目描述：
1.快慢指针法
其实这个题我们思考一下，如果它是一个环的话，那我们遍历一遍它就进入死循环了，如果不是环，就可以出来，但是这我们又无法知道它是否是死循环。有可能数据无限大，所以我们不能简单的凭借是否死循环来做这道题，那么就想，我们高中物理学过追及相遇问题，那么我们同样可以将思路带入到这里来。
我们是这样想的，使用两个指针，一个一次走一步，一个一次走两步。如果有环的话，那么快慢最终会相遇（下面有证明），如果无环，那么最终fast或者fast->next中必然有一个为空，因为有奇偶的讨论。所以顺着这个思路，这个代码很容易就写出来了
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { struct ListNode* slow=head; struct ListNode* fast=head; while(fast && fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) { return true; } } return false; }
2.证明快慢指针是可行的
我们了解了上面的解法以后，我们也会产生一些疑惑，为什么快慢指针一定相遇，这里和物理中的追及相遇问题不一样的是，追及相遇问题是连续的，而这个问题是离散的。
我们的问题归纳一下就是：
slow一次走一步，fast一次走两步
1.slow和fast最后一定会相遇吗？有没有可能不会相遇？
2.slow一次走一步，fast一次走三步行不行？
slow一次走一步，fast一次走四步行不行
请证明：
我们先给出结论：
slow一次走一步，fast一次走两步一定可以相遇
我们可以这样思考
假设当slow刚进环的时候，fast和slow距离为N
那么fast和slow每一次他们的距离就-1，距离为N-1N-2 N-3...........0
最终一定会变为0。也就是相遇了。
所以一定可以相遇
那么slow一次一步，fast一次三步可不可以呢？
我们同样假设slow刚进环的时候相距为N
那么它们最终的距离就为N-2 N-4 N-6..........
我们可以看出来他们最终是要分情况讨论的，他们距离最近时候要么为0 要么为-1
0代表相遇，但是-1呢？-1其实代表着fast反超了slow一步
这时候我们假设环的总长度为C
那么我们此时fast和slow就相距为C-1的长度，而走一次他们的距离就减2
那么我们也可以看出来，当C为偶数的时候，永远不可能相遇
当C为奇数的时候才会相遇
所以fast一次走三步的时候还取决于N和C的长度。不一定会相遇
同样的，当一次走四步的时候也是同理的，不一定相遇
三、力扣第142题：环形链表Ⅱ
题目链接：142. 环形链表 II - 力扣（Leetcode）
题目描述：
1.解题思路
对于这道题，难点就在于如何求出这个入口，我们先给出结论
一个指针从相遇点走，一个指针从开头走，最终这两个指针将会在入口相遇
对于这个题目我们得先画图思考一下，如下图所示，假设这就是我们的链表
设环为C长度，他们相遇点距离入口为X长度，他们的起始点距离入口为L长度
已经fast的路程为L+X+N*C，slow的路程为X+L
slow的路程很简单，因为slow进入环以后，fast一定会在一圈之内追上slow，所以为L+X
这里大家比较疑惑的就是fast的路程，其实fast的路程是这样得到的，首先fast得先走一个L，这个毋庸置疑，然后当slow进环的时候，fast刚好走了一段距离，现在是fast正在追slow，这个时候slow走了x的时候，fast也刚好追上slow。而fast这时候其实就相当于走了N*C+X路程了，因为有可能直线特别大，圈特别小，fast在圈内走了好多圈了，slow还没有进来。所以走了N*C圈
而又由于fast的速度是slow的两倍，时间相同，那么路程肯定也是两倍
所以得出
N*C+X+L=2*（X+L）
然后得出
N*C-X=L
而这个公式的含义就是
一个指针从相遇点走，一个指针从开头走，最终这两个指针将会在入口相遇
2.代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* fast=head; struct ListNode* slow=head; while(fast && fast->next) { fast=fast->next->next; slow=slow->next; if(fast==slow) { struct ListNode* meet=slow; while(meet!=head) { meet=meet->next; head=head->next; } return meet; } } return NULL; }
总结
本小节讲解了三个经典的力扣题21.合并两个有序链表、141.环形链表、142.环形链表Ⅱ，希望大家都学会
如果对你有帮助，不要忘记点赞加收藏哦！！！
想获得更多有优质的内容，那么一定要关注我哦！！！
