Happy Coding: [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?

Solution 1: Hash, linear running time with extra linear space.
Since here we only need to determine whether an element exists, HashSet is preferable. The advantage of this approach is its simplicity, while it uses extra linear space.

/**
 * 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) {
        HashSet<ListNode> set = new HashSet<ListNode>();
        ListNode p = head;
        
        while (p != null) {
            if (set.contains(p)) {
                return p;
            } 
            set.add(p);
            p = p.next;
        }
        
        return null;
    }
}

Solution 2: Two pointers, quadratic running time in the worst case.
In this solution, we first decide whether it has a cycle by using two pointers, the slower pointer, which moves one step at a time, and the faster pointer, which moves two steps at a time. If there is a cycle, these two pointers will collide inside the cycle.
Next, we use two new pointers: one pointer will move from the head to the beginning of the cycle, and the second pointer will simply move along the cycle from the collision point. The beginning of the cycle will be the first node such that when the second pointer moves along the cycle, it will collide with the beginning of the cycle.
Assuming the length of the cycle is L, the running time will be L(n - L), where n is the total length of the list. That is, it has quadratic running time in the worst case.

/**
 * 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) {
        ListNode slow = head;
        ListNode fast = head;

        do {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);
    
        ListNode collision = fast;        
        ListNode p = head;
        
        while (p != null) {
            ListNode q = collision;
            do {
                if (q == p) {
                    return p;
                }
                q = q.next;
            } while (q != collision);
            p = p.next;
        }
        
        return null;
    }
}

Solution 3: Two pointers, linear running time.
This is the optimal solution. However, it is not as obvious as the above ones.
The key observation is that we move two pointers at a pace of 1 step and 2 steps, called as the slower pointer and the faster pointer, respectively, then the first collision point of these two pointers, if it exists, has the "same" distance as the head node to the beginning of the cycle.
To see this, assume that the length of the list outside (resp. inside) the cycle is k (resp. L). Then when the slower pointer arrives at the beginning of the cycle, it has marched k steps, while the faster pointer has marched 2k steps. The latter implies that the faster pointer is k % L steps ahead of the slower pointer (and ahead of the beginning of the cycle as well). In other words, the slower pointer is (L - k % L) steps ahead of the faster pointer. Note that each time, the faster pointer is one step closer to the slower pointer, so after (L - k % L) times of marching, they will meet, more importantly, they are meeting for the first time, since it is the first time for the slower pointer marching inside the cycle (note that L - k % L <= L). It is easy to see that they first collide at the point that is (L - k % L) steps ahead of the beginning of the cycle (that is where the slower pointer will be, hence the faster one). In other words, the first collision point of the slower pointer and the faster pointer is k % L steps behind the beginning of the cycle.
Now, we use two new pointers, both marching at a pace of 1 step at a time. We march one of them from the head of the list, and the other from the above collision point. We call them the outsideCycle pointer and the insideCycle pointer, respectively. When the outsideCycle pointer first enters the cycle, it has marched k steps, so is the insideCycle pointer. Where will the insideCycle pointer be? Well, initially, the insideCycle pointer lies at the first collision point of the slower pointer and the faster pointer, where the collision point is k % L steps behind the beginning of the cycle. With k more steps marched, the insideCycle pointer will lie exactly at the beginning of the cycle.
Hence, we've found the beginning of the cycle.

/**
 * 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) {
        ListNode slow = head;
        ListNode fast = head;
        
        do {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);
        
        ListNode outsideCycle = head;
        ListNode insideCycle = fast;
        
        while (outsideCycle != insideCycle) {
            outsideCycle = outsideCycle.next;
            insideCycle = insideCycle.next;
        }
        
        return insideCycle;
    }
}

Happy Coding

Tuesday, May 19, 2015

[LeetCode] Linked List Cycle II

No comments:

Post a Comment