Linked List Cycle II

Medium Problem 55 of 151 Java and Python

Problem

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

Example 1

Input: head = [3, 2, 0, -4], the tail links to index 1
Output: the node with value 2

Example 2

Input: head = [1], no cycle
Output: null

Constraints

0 ≤ number of nodes ≤ 10⁴
Follow-up: O(1) memory.

Explanation

First detect the cycle with slow and fast pointers. Say the cycle starts a steps from the head and they meet b steps into the cycle of length c. Fast travelled twice as far, which works out to a = (k - 1)·c + (c - b).

In words: walking a steps from the head reaches the cycle start, and so does walking a steps from the meeting point. So restart one pointer at the head, move both one step at a time, and they meet at the start of the cycle.

Approach 1 · Naive

First repeated node

Time O(n)
Space O(n)

Walk the list storing visited nodes. The first node you see twice is where the cycle begins.

For each node: if it is already in the set, return it; otherwise add it.
Return null if the list ends.

Java

import java.util.*;

class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<>();
        for (ListNode node = head; node != null; node = node.next) {
            if (!seen.add(node)) {
                return node;
            }
        }
        return null;
    }
}

Python

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        seen = set()
        while head:
            if head in seen:
                return head
            seen.add(head)
            head = head.next
        return None

Approach 2 · Optimal

Floyd: meet, then restart from the head

Time O(n)
Space O(1)

After slow and fast meet, move a pointer from the head and one from the meeting point at the same speed; they meet at the cycle start.

Run slow (1 step) and fast (2 steps) until they meet; if fast reaches the end, return null.
Set p = head. While p != slow, move both one step.
Return p.

Java

class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode p = head;
                while (p != slow) {
                    p = p.next;
                    slow = slow.next;
                }
                return p;
            }
        }
        return null;
    }
}

Python

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                p = head
                while p is not slow:
                    p, slow = p.next, slow.next
                return p
        return None

Complexity compared

Approach	Time	Space
Naive First repeated node	O(n)	O(n)
Optimal Floyd: meet, then restart from the head	O(n)	O(1)

Key takeaways

Same trick finds the duplicate in Find the Duplicate Number, by treating values as next pointers.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem