【LeetCode题目详解】（三）21.合并两个有序链表、141.环形链表、142.环形链表Ⅱ
目录
一、力扣第21题：合并两个有序链表
解法思路
代码一
代码二
代码三
二、力扣第141题：环形链表
1.快慢指针法
2.证明快慢指针是可行的
三、力扣第142题：环形链表Ⅱ
1.解题思路
2.代码
总结
一、力扣第21题：合并两个有序链表
题目链接：21. 合并两个有序链表 - 力扣（Leetcode）
题目描述：
解法思路
对于这个题目而言，我们肯定是很熟悉的，因为我们已经讲解过一个合并两个有序数组的题目了。这道题完全只是将数组改成了链表。那么我们在链表中使用的方法是尾插法。谁小先插谁
我们先过一遍思路吧，首先我们先看这个图
我们的思路是这样的，先创建两个指针,newHead和tail，用于记录最后返回的链表的头和尾，我们让他们一开始指向NULL
然后我们看如果list1->val
然后我们一直循环下去
当只要有一个链表为空以后，那么直接将两个链表链接起来即可
这就是我们的大体思路，但是需要注意的是，有可能一开始会有其中一个链表是空链表，那么这种我们可以一开始做一个判断，只要有一个为空，返回另外一个链表即可
代码一
/*** 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->valval){//链表头为空，这是第一次插入，需要特殊处理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->valval){//尾插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->valval){//尾插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题：环形链表
题目链接：141. 环形链表 - 力扣（Leetcode）
题目描述：
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.环形链表Ⅱ，希望大家都学会
如果对你有帮助，不要忘记点赞加收藏哦！！！
想获得更多有优质的内容，那么一定要关注我哦！！！