Leetcode and Lintcode

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

Leetcode link
Lintcode link

Solution:

We can use two pointers to go through the list.
The fast pointer has the twice speed as the slow pointer.
If their is a circle, they will meet eventrually.
Assume the length of the head to the loop start point is k, and the loop size is n.
When the slow pointer get the beginning loop node, it has gone k nodes, and the fast pointer go 2k nodes.
The distance between the two pointers is k % n, in other sise is (n - k % n).
When the fisrt meet on the circle, they will meet at the point which is (n - k % n) nodes far from the beginning loop point.
Then let the slow pointer go back to the head, and they start to move with the same speed.
When the slow pointer goes k nodes distance, it get to the beginning loop point.
The fast pointer goes further (k % n) distance, which is (n - k % n ＋ k % n) = n, so it is also the beginning loop point, and also they meet up.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*************************************************************************
	> File Name: LinkedListCycleII.java
	> Author: Yao Zhang 
	> Mail: psyyz10@163.com 
	> Created Time: Fri 20 Nov 11:52:45 2015
 ************************************************************************/

public class LinkedListCycleII{
	public ListNode detectCycle(ListNode head) {
        if (head == null)
            return 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;
        
        slow = head;
        
        while (fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        
        return fast;
    }
}