Linked List Cycle

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Hash Approach#

Analogy: Like marking every door you pass; if you see a marked door again, you are in a loop.

Store every visited node pointer in a hash set. Before visiting each node check whether it is already in the set — if yes, a cycle exists. The drawback is O(n) extra space for the hash set; the advantage is simplicity and the ability to also identify the cycle-entry node.

bool hasCycle(ListNode* head) {
    unordered_set<ListNode*> visited;
    while(head) {
        if(visited.count(head)) return true;
        visited.insert(head);
        head = head->next;
    }
    return false;
}

Time Complexity: O(n)

Space Complexity: O(n) (hash set)

Floyd's Cycle Detection: Hare-tortoise method#

Analogy: A fast runner will eventually lap the slow runner on a circular track if a cycle exists.

Use two pointers: slow moves one step at a time, fast moves two steps. If no cycle exists fast or fast->next becomes null and we return false. If a cycle exists fast will "lap" slow and both pointers will eventually point to the same node. This eliminates the hash set and reduces space to O(1), at the cost of needing a separate pass to find the exact cycle-entry node if that is also required.

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fastPointer = head;
        ListNode* slowPointer = head;

        while(fastPointer && fastPointer->next)
        {
            fastPointer = fastPointer->next->next;
            slowPointer = slowPointer->next;
            if(slowPointer==fastPointer)
                return true;
        }
        
        return false;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)