Leetcode: Linked List Cycle

Given a linked list, determine if it has a cycle in it.

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

Understand the problem:
This is a classic code interview problem. Before we jump into any solutions, let's take a look at the question. The question asks for if a linked list have a cycle in it. 

So we must understand what is a cycle in a linked list? A cycle in the linked list means the trail of the linked list points to another previous node. For instance, 1 -> 2 ->3 ->4 ->5 ->2. 
Note that cycle is prohibited in a linked list anyway because it will make the linked list never ends. Remember that for a linked list, we only know the current node and its next. 

Consequently, we can define several more examples to illustrate the problem.
1 -> 2  ->3  -> 4, has no cycle
 1 -> 3 ->4 -> 1, has a cycle


Naive Solution:
As a straight-forward solution, it is very easy to see that for a linked list without cycle, all nodes will never repeat; otherwise, we must see a repeated node. So we can use a Hash Table to store the visited nodes. If not see before, we put into the hash table, else the linked list must have a cycle. 

Before we decide to implement the algorithm, let's analyze the solution. For the time complexity, it is O(n) because the linked list is traversed only once. The space complexity is O(n) as well because it needs at most n key-value pairs to store the visited nodes. 


A better Solution:
Since this question asks for solving it without using extra space, we need to devise another solution without using hash table. 

Most of the linked list questions can be solved by using two pointers, either with different speed, or the same but different distance. We can use the similar idea to solve this question. 

Use two pointers. One moves one node at a time, while the other moves two at a time. If the linked list has a circle, they must meet at the circle. It is easy to understand the idea. One pointer moves one step while the other moves two equals to one stands and the other moves one step a time to chase him. In a circle, two pointers must meet somewhere. 

Code (Java):

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast !=null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) return true;
        }
        return false;
    }
}

Discussion:
Now let's analyze the complexity of this solution. If the linked list have a cycle, we are sure that the collision point must be within the cycle. In worst case, when the slower pointer is at the entrance of the cycle and faster pointer is just one step ahead. The fast pointer must chase the length of cycle steps to catch up the slow pointer. In the best case, when the slow pointer is at the entrance of the cycle, the fast pointer is one step behind it, then they will meet at the next step. In this case, it takes 1 step to catch up the slow pointer. Therefore, on the average case, the faster pointer takes O(n) steps to catch up the slow pointer.

Summary:
Determine a linked list has a cycle is a very classic interview problem. The solution is tricky but not hard to understand. Most of the linked list problems can be solved by using two pointers. 

Last but not least, when you use two pointers, make sure the check the fast pointer will not "overflow", i.e, move to a wild address. Make sure you understand the Line 19.