Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Linked List Cycle II

Linked List Cycle II

Master this topic with zero to advance depth.

Linked List Cycle II

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

Visual Representation

3 -> 2 -> 0 -> -4 ^ | +----------+ Cycle starts at node with value 2.
Medium

Examples

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Approach 1

Level I: HashSet

Intuition

Store visited nodes in a set. The first node we encounter that is already in the set is the start of the cycle.

⏱ O(N)💾 O(N)
java
public ListNode detectCycle(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    while (head != null) {
        if (visited.contains(head)) return head;
        visited.add(head); head = head.next;
    }
    return null;
}
Approach 2

Level II: Node Marking (Magic Value)

Intuition

If we can modify the node values, we can mark each visited node with a special value (outside the problem's constraints). If we encounter a node already marked with that value, it's the start of the cycle.

⏱ O(N)💾 O(1)

Detailed Dry Run

List: 3 -> 2 -> 0 -> -4 (back to 2).

  1. 3.val = 100001.
  2. 2.val = 100001.
  3. 0.val = 100001.
  4. -4.val = 100001.
  5. Next is 2, whose val is 100001. Cycle start found.
java
public ListNode detectCycle(ListNode head) {
    while (head != null) {
        if (head.val == 100001) return head;
        head.val = 100001; head = head.next;
    }
    return null;
}

⚠️ Common Pitfalls & Tips

This modifies the original list. In many real-world or interview scenarios, modifying the input data is not allowed unless specified.

Approach 3

Level III: Floyd's Cycle-Finding Algorithm

Intuition

Detect cycle first, then reset one pointer to head and move both at speed 1 to find meeting point.

Visual Trace

D = Distance to cycle, S = Meeting point from start, C = Cycle length. Moving D steps from head and D steps from meeting point hits cycle start.
⏱ O(N)💾 O(1)
java
public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
        if (slow == fast) {
            ListNode slow2 = head;
            while (slow2 != slow) { slow = slow.next; slow2 = slow2.next; }
            return slow;
        }
    }
    return null;
}
← Previous QuestionRemove Duplicates from Sorted List
Next Question →Remove Linked List Elements