LeetCode---环形链表 II

LeetCode---环形链表 II

首先要解决这个题，我们先要明白我们要考虑的情况

如果链表没有环，则直接返回null

ListNode fast=head; ListNode slow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; if(fast==slow){ break; } }

if(fast==null||fast.next==null){ return null; }

如果有环，那我们也要考虑两种情况

圈大

从上面的图片中我们可以看出，当fast一次走两步，slow一次走一步的时候，我们会发现，

slow所走的路程是X+C-Y

fast所走的路程是X+C+C-Y

注意：慢指针不会走了很多圈才会被追上，实际上慢指针最多走半圈

如果实在想不懂，可以看看上面的图，一步一步带入进去

由于fast是一次性走两步，slow是一次性走一步

所以fast所走的路程是slow所走路程的两倍

slow所走的路程是X+C-Y

fast所走的路程是X+C+C-Y

所以我们可以列出等式 X+C+C-Y=2*(X+C-Y)

化简之后就可以看到

X==Y

由于X==Y

所以我们让指针1和指针2同时走，那么它俩就会在入环的第一个节点相遇

圈小

所谓的圈小，就是当slow进环的时候，fast已经走了很多圈了

此时当slow和fast相遇的时候，走的路程分别是

slow：X+C-Y

fast：X+N*C+C-Y

由于fast所走的路程是slow的两倍

所以

2*(X+C-Y)=X+N*C+C-Y

化简后得到

x+c-y=nc

x=(n-1)c+y

当n==0的时候，X==Y，恰好是圈大的情况

当fast走了n-1圈后，依旧是回到相遇点，然后再加上个Y，正好是入环的第一个节点

假设圈的长度是2，当slow走了X的一半的时候，fast恰好入环

此时，slow每走一步，fast就走一圈

完整版代码：

public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow=head; ListNode fast=head; //首先在环中找到相遇的点 while(fast!=null&&fast.next!=null){ slow=slow.next; fast=fast.next.next; if(slow==fast){ break; } } //没找到环的情况 if(fast==null||fast.next==null){ return null; } //定义一个新节点，从头开始走，每次走一步，fast也每次走一步 //当cur和fast相等的时候，跳出循环，此时这个节点就是入环的第一个节点 ListNode cur=head; while(cur!=fast){ cur=cur.next; fast=fast.next; } return cur; } }