首页 > 代码库 > 【leetcode刷题笔记】Linked List Cycle II
【leetcode刷题笔记】Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null
.
Follow up:
Can you solve it without using extra space?
判断一个链表是否有环。
题解:
设置两个指针p1和p2;
p1每次走一步,p2每次走两步,如果在这个过程中,p2为空,则没有环;否则两个指针必然相遇,则有环;
接下来找环的起点,将p1挪动到链表起始,p2保持在两指针相遇的地方不动,然后p1和p2分别每次走一步,则下一次相遇的地方为环的起点。
先贴代码如下:
1 class ListNode { 2 int val; 3 ListNode next; 4 ListNode(int x) { 5 val = x; 6 next = null; 7 } 8 } 9 10 public class Solution {11 public ListNode detectCycle(ListNode head) {12 ListNode p1 = head;13 ListNode p2 = head;14 15 while(p2 != null){16 p1 = p1.next;17 p2 = p2.next;18 if(p2 != null)19 p2 = p2.next;20 else 21 return null;22 if(p1 == p2)23 break;24 }25 26 if(p2 == null)27 return null;28 p1 = head;29 while(p1 != p2){30 p1 = p1.next;31 p2 = p2.next;32 }33 return p1;34 }35 }
证明如下(证明参考:http://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work)
如上图所示,假设从链表起点到环的起点距离为m,从环的起点到p1和p2第一次相遇的地方距离为k,环的长度为n。设第一次相遇的时候p1走过了S步,则p2走过了2S步,所以
S = m + pn + k (1)
2S = m + qn + k (2)
其中p1绕圆走过了完整的p圈,p2绕圆完整的走过了q圈。
(1)式代入(2)式中得:2(m+pn+k) = m+qn + k -> m+k = (q - 2p)n (3)
对于任意一个链表m和n是固定的,所以我们只要证明存在整数p,q,k使得(3)式成立即可。
去p = 0, k = mn-m, q = m, 则(3)式成立,所以p1,p2一定会相遇在距离环的起点(mn-m)的地方。
接下来证明如果使得p1回到环的起点,p2保持不动,两个指针以相同的速度前行,则下一次相遇的地方一定是环的起点。
从(3)式可以看出,m+k是环的长度的整数倍,所以p2从相遇的地方走m步,一定回到环的起点,而p1从链表起点走m步也走到环的起点,所以p1和p2以相同的速度前进,下一次相遇的地方一定的环的起点。
证毕。