【LeetCode】两道环形链表题

题目链接1：力扣

题目链接2： 力扣

目录

 一、环形链表

 二、环形链表II

 一、环形链表

别看题目这么长就被吓到了，其实代码写起来很简单。

但是也别想的太简单了，可别用遍历链表找NULL的方法做，会陷入死循环的。

 这些都是有可能的成环情况，所以也不能用记录开始成环的结点那个思路。

继续往下看

思路：用快慢指针解决是最简单的，因此这题也就演变为快慢指针的相遇问题

慢指针走一步，快指针走两步，如果慢指针和快指针相遇了就说明此链表是带环

代码实现： 

bool hasCycle(struct ListNode *head) {    struct ListNode *fast,*slow;    fast=slow=head;    while(fast && fast->next)//链表是奇数还是偶数    {slow=slow->next;fast=fast->next->next;if(slow == fast){    return true;}    }    return false;}

时间复杂度：O(N)，其中N是链表中的节点数。 

代码写出来了是不是感觉很神奇！

思考以下问题帮助你更好的理解这个思路 

思考：为什么快指针每次走两步，慢指针走一步可以？

解释：假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。
此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情
况，因此在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

 

思考：快指针走别的步数行不行？

解释：假设快指针每次走3步，慢指针每次走1步，此时快指针肯定先进环，慢指针后面才进环。假设慢指针进环时快指针和慢指针之间的距离是N，如下图展示。

	偶数	奇数
距离	N	N
距离	N-2	N-2
距离	N-4	N-4
距离	......	......
距离	4	3
距离	2	1
距离	0	-1

所以当N是偶数的时候快慢指针就能追上，当N是奇数的时候，快指针刚好将慢指针套圈了，此时就追不上了。以此类推快指针走四步也是不行的。

所以只有快指针走2步，慢指针走1步才行，因为每走1步距离就缩小1，及时套圈了两个指针也在相同的位置。

 二、环形链表II

这个题当然还是用快慢指针来做啦，但是这题有点不好理解，注意内容往下看哦！

 假设：快指针和慢指针在meet点相遇 ，环入口点为E，起始点为head，head到E的距离是a，E到meet的距离是b，meet到E的距离是c，环的长度为R。所以c=R-b。

慢指针（slow）相遇时所走长度：a+b

快指针（fast）相遇时所走长度：a+b+nR（n>=1）

为什么R要乘个n倍呢？

因为：环有可能很小的时候，fast有可能走了好多圈才和slow相遇。

根据快指针走的长度是慢指针的2倍。

这时，我们就可以得到一个公式：

把这个公式再进一步化简得：  

所以一个指针从相遇点开始走，一个指针从头开始走，它们会在入口点处相遇。

代码实现：

struct ListNode *detectCycle(struct ListNode *head) {     struct ListNode *slow,*fast; fast=slow=head; while(fast&&fast->next) {     slow=slow->next;     fast=fast->next->next;     if(fast==slow)     {  struct ListNode *meet=slow;  while(meet!=head)  {      meet=meet->next;      head=head->next;  }return meet;     } } return NULL;}

这个题还可以用两个链表相交来做

思路：将相遇点的下一个位置作为newhead，meet作尾让后置空，这个就转化为了newhead和head两个链表相交求交点的问题了。 具体可以参照我下面的这篇博客【LeetCode】相交链表——面试经典题目_爱偷懒的猫(๑>؂<๑）的博客-CSDN博客

代码实现： 

struct ListNode *detectCycle(struct ListNode *head) {     struct ListNode *slow,*fast; fast=slow=head; while(fast&&fast->next) {     slow=slow->next;     fast=fast->next->next;     if(fast==slow)     {  struct ListNode *meet=slow; struct ListNode* newhead=meet->next; struct ListNode *curA=newhead; struct ListNode *curB=head; meet->next=NULL; int lenA=1,lenB=1,len=0; while(curA->next) {     curA=curA->next;     lenA++; } while(curB->next) {     curB=curB->next;     lenB++; }  struct ListNode* shortlist=head,*longlist=newhead; if(lenB>lenA) {     longlist=head;     shortlist=newhead; } int gap=abs(lenA-lenB); while(gap--) {     longlist=longlist->next; } while(shortlist!=longlist) {     shortlist=shortlist->next;     longlist=longlist->next; } return shortlist;     } } return NULL;}

今天的题解就分享到这

觉得内容有用的话就给博主三连吧！！！