Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
Input: A -> B -> C -> D -> E -> C [the same C as earlier]
Output: C
Hint
- There are really two parts to this problem. First, detect if the linked list has a loop. Second, figure out where the loop starts.
- To identify if there's a cycle, try the "runner" approach described on page 93. Have one pointer move faster than the other.
- You can use two pointers, one moving twice as fast as the other. If there is a cycle, the two pointers will collide. They will land at the same location at the same time. Where do they land? Why there?
- If you haven't identified the pattern of where the two pointers start, try this: Use the linked list 1->2->3->4->5->6->7->8->9->?, where the? links to another node. Try making the? the first node (that is, the 9 points to the 1 such that the entire linked list is a loop). Then make the ? the node 2. Then the node 3. Then the node 4. What is the pattern? Can you explain why this happens?
Solution
本題需要我們判斷鏈表內(nèi)是否有環(huán)缩宜，并且返回環(huán)的起始結(jié)點。依然是用雙指針的方法圆兵，慢指針每次移動1步超凳，快指針每次移動2步，若有環(huán)，則兩個指針必然會中途相遇。然后將其中一個指針從頭開始遍歷，這時兩個指針同步移動1虫蝶，當它們再次相遇時便是環(huán)的起始結(jié)點。
public ListNode detectCycle(ListNode head) {
ListNode slow = head, 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;
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
