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?
A:
就用CC150上的那道题目。 先slow and fast runner meet后,再把fast 放到开头,重新跑(速度变慢)
Mistakes:
1: update fastRunner 到链表头的时候,忘了把slowRunner也往下走一个。
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { if(head == null || head.next == null) return null; ListNode slow = head, fast = head.next; while(slow!= fast){ slow = slow.next; fast = fast.next; if(fast==null || fast.next == null) return null; fast = fast.next; } slow = head; fast = fast.next; while(slow!= fast){ slow = slow.next; fast = fast.next; } return slow; } }证明如下:
假设前面不重复的链表长度为k, # of nodes in circle is n.
at time t = k+a (where a is the number of nodes slow have run in the circle)
=======> a+k = 2(k+a) - x*n , (x倍的n), 取代了求模运算
则有 a+k = x*n
那么,fast再走 k时间,也就是再走 (a +k) 的时候,就回到了原点。
这里有一个注意的地方就是,(当我们重新计数的时候,slow=head时,已经表明我们走了一步了。因此我们需要把fast也前进一步。
Learned:
No comments:
Post a Comment