LInked List Cycle II

142.Linked List Cycle II

Linked List

Two Pointers

Hash Table

Problem Statement:

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null. 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.

Example:

Input:

head = [3,2,0,-4], pos = 1

→

Output:

tail connects to node index 1

Algorithm:

1. Use Floyd's Tortoise and Hare with two pointers
2. Move tortoise and hare until they meet
3. Reset one pointer to head and move both
4. Second meeting point is cycle start

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

public ListNode detectCycle(ListNode head) {
    // Initialize tortoise and hare pointers
    ListNode tortoise = head;
    ListNode hare = head;

    // Move tortoise one step and hare two steps
    while (hare != null && hare.next != null) {
        tortoise = tortoise.next;
        hare = hare.next.next;

        // Check if the hare meets the tortoise
        if (tortoise == hare) 
            break;
    }

    // Check if there is no cycle
    if (hare == null || hare.next == null) 
        return null;

    // Reset hare pointer to head for finding cycle start
    hare = head;

    // Move both pointers one step until they meet again
    while (tortoise != hare) {
        tortoise = tortoise.next;
        hare = hare.next;
    }

    return tortoise;
}

// HashSet Method O(n) space
public ListNode detectCycleONSpace(ListNode head) {
    if (head == null) {
        return head;
    }
    
    Set seen = new HashSet();
    ListNode curr = head;
  
    while (curr.next != null) {
        seen.add(curr);
        curr = curr.next;
        
        if (seen.contains(curr)) {
            return curr;
        }
    }
    
    return null;
}

Python Solution:

def detectCycle(self, head: ListNode) -> ListNode:
    if not head:
        return None
        
    tortoise = head
    hare = head
    
    while hare and hare.next:
        tortoise = tortoise.next
        hare = hare.next.next
        
        if tortoise == hare:
            hare = head
            while tortoise != hare:
                tortoise = tortoise.next
                hare = hare.next
            return tortoise
            
    return None

C++ Solution:

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        if(!head) return nullptr;
        
        ListNode *tortoise = head;
        ListNode *hare = head;
        
        while(hare && hare->next) {
            tortoise = tortoise->next;
            hare = hare->next->next;
            
            if(tortoise == hare) {
                hare = head;
                while(tortoise != hare) {
                    tortoise = tortoise->next;
                    hare = hare->next;
                }
                return tortoise;
            }
        }
        
        return nullptr;
    }
};