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?

Analysis:
One way to solve this problem is to traverse the linked list while keeping a vector storing the address of each node visited. For each node we visit, we first check if the address of that node is already in our vector. If yes then we have run into a previously visited node, hence there is a cycle. If we do not detect any cycle until the NULL node, then the list has no cycle. This algorithm takes space and runs in time.

A better algorithm is based on the following observation: if we have a fast node that traverse the list two nodes at a time, and a slow node that traverse the list one node at a time, then the linked list has a cycle if and only if the fast node and the slow node collide before they run into the NULL node at the end. One direction of this claim is easy to show: if the two nodes collide, then there must be a cycle in the list since otherwise the fast node will arrive at the NULL node and there won’t be any collision. Contradiction.

On the other hand, if there is cycle in the list, then suppose that the beginning of the cycle starts at node , then after steps, the slow node will arrive at the beginning of the cycle whereas the fast node is already nodes into the cycle, and now both of them will be trapped in the cycle. Suppose the cycle has nodes, then since the fast node catches up with the slow node one node at a time, after steps the fast node will collide with the slow node.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        
        ListNode *fast, *slow;
        fast = slow = head;
        while (fast != NULL && fast->next != NULL)
        {
            //first increment the fast and slow pointers
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow) //there is collision!
                break;
        }//endwhile
        if (fast == NULL || fast->next == NULL)
            return false;
        else
            return true;
    }
};