Topics › Linked List › Medium Problems of LL

Find the starting point in LL

Medium TUF ID 2847 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given the head of a singly linked list that may contain a loop: the last node’s next points back to some earlier node instead of being null. Return the node where the loop starts, that is, the first node that is reached a second time when walking from head. If there is no loop, return null. Do not modify the list.

As in the loop-detection problem, only node identity matters; equal values in different nodes are irrelevant. The tests describe a loop by the index pos the tail points to, but pos is hidden from the solution.

Constraints: 0 ≤ n ≤ 10^4 nodes, values fit in a 32-bit signed integer.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Example 1

head = 3 -> 2 -> 0 -> -4,  tail points to index 1
answer = the node holding 2      // walking 3, 2, 0, -4 the next node is 2 again

Example 2

head = 1 -> 2,  tail points to index 0
answer = the node holding 1      // the head itself starts the loop

Example 3

head = 1 -> 2 -> 3,  no loop
answer = null

Approach 1: Brute force, remember visited nodes

Intuition. Walk the list and remember every node seen so far. The first node we meet that is already in the set is, by definition, the first repeated node, which is exactly the loop’s starting point: everything before it was visited once, and from it onwards the walk cycles.

Algorithm.

1. Create an empty HashSet<ListNode>.
2. Walk from head. For each node, try to add it to the set.
3. If add returns false, return that node.
4. If the walk reaches null, return null.

static ListNode bruteForce(ListNode head) {
    Set<ListNode> seen = new HashSet<>();
    for (ListNode t = head; t != null; t = t.next) {
        if (!seen.add(t)) return t;        // add returns false for a node object already in the set
    }
    return null;
}

Complexity. Time O(n): each node is visited at most twice. Space O(n): the set stores every node on the path.

This gives the right node immediately, but needs memory proportional to the list. The classic follow-up is to do it with two pointers and no extra memory, which requires understanding where the slow and fast pointers meet.

Approach 2: Optimal, Floyd’s algorithm with a reset

Intuition. Run the tortoise-and-hare detection first: slow moves one node, fast moves two, until they meet somewhere on the loop. Now the surprising fact: if you put a new pointer at head and move it and slow one node at a time, they meet precisely at the start of the loop.

Here is why. Let L1 be the number of nodes from head to the loop’s start, and C the loop length. When slow has taken L1 steps it is at the loop start; fast has taken 2 L1 steps and is L1 mod C nodes into the loop. The gap from slow forward to fast is therefore L1 mod C; the gap from fast forward to slow is C - (L1 mod C). Since fast gains one node per step, it catches slow after exactly C - (L1 mod C) more steps. So the meeting point is C - (L1 mod C) nodes past the loop start, which means it is L1 mod C nodes before the loop start when walking forward around the loop. Walking L1 more steps from the meeting point therefore lands exactly on the loop start (because L1 steps around the loop equals L1 mod C steps plus whole laps). A pointer starting at head needs the same L1 steps to reach the loop start. Move both one step at a time and they coincide there.

Algorithm.

1. Set slow = head, fast = head.
2. While fast and fast.next are non-null: move slow by one, fast by two. If they meet, go to step 3.
3. Set entry = head. While entry != slow, move both one step. Return entry.
4. If the first loop exits because fast hit null, return null.

static ListNode optimal(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {                // a loop exists; now locate its entry
            ListNode entry = head;
            while (entry != slow) {        // both advance one step at a time
                entry = entry.next;
                slow = slow.next;
            }
            return entry;
        }
    }
    return null;                           // fast reached the end: no loop
}

Dry run on 3 -> 2 -> 0 -> -4, tail pointing to the node 2 (so L1 = 1, C = 3):

Complexity. Time O(n): detection takes at most L1 + C ≤ n slow steps plus one extra lap, and the locate phase takes L1 steps. Space O(1): three pointers.

Both approaches return the same node object; the Java tests compare the results with == against the node at index pos and also run a list of six equal values to prove that identity, not value, is what is detected.

Edge cases and pitfalls

• No loop. fast or fast.next becomes null; return null. Never run the locate phase in that case.
• Loop starting at the head. L1 = 0, the meeting point can be the head itself, and the locate phase ends immediately with entry == slow == head.
• Self-loop on a single node. slow and fast both land on the node after one step, and the locate phase returns it.
• Empty list. fast is null; return null.
• Resetting the wrong pointer. After the meeting, one pointer goes back to head and the other stays at the meeting point. Resetting both, or moving the reset pointer two steps, breaks the proof.
• Comparing values. entry != slow must compare node references. Lists like 3 -> 3 -> 3 -> 3 -> 3 -> 3 with a loop would otherwise stop at the wrong node.
• Returning the meeting point. The place where slow and fast first meet is generally not the loop start; the second phase is required.

Related problems

• Detect a loop in LL is the first phase of this algorithm on its own.
• Length of loop in LL measures C by walking once around from the meeting point.
• Middle of a LinkedList [TortoiseHare Method] is the simplest use of the slow and fast pointer pair.
• Find the intersection point of Y LL also compares node references rather than values.