☕ DSA Java Articles

Topics › Linked List › Medium Problems of LL

Find the starting point in LL

Medium TUF ID 622 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the head of a singly linked list, return the node where its loop begins, or null if the list has no loop. The loop starts at the first node that you would visit twice when following next pointers from the head. Do not modify the list.

A list with a loop looks like the Greek letter rho: a straight “tail” of L nodes that leads into a circle of C nodes. The answer is the node where the tail joins the circle. When L = 0, the head itself is on the circle and is the answer.

Constraints: up to 10^4 nodes in the LeetCode version. The follow-up asks for O(1) extra memory.

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

Example 1

3 -> 2 -> 0 -> -4
     ^          |
     +----------+
answer = the node holding 2     // the tail is just [3], then the circle 2 -> 0 -> -4 -> 2

Example 2

1 -> 2 -> 3 -> null
answer = null                   // no loop

Approach 1: Brute force, the first node seen twice

Intuition. Walk the list and remember every node in a hash set. The walk passes the L tail nodes once each, then enters the circle at its starting node s and goes around: s, then the other C - 1 circle nodes, then s again. Every node before that second visit of s was new, so s is the very first node we find already in the set. That makes “first repeated node” and “start of the loop” the same thing.

Algorithm.

  1. Create an empty HashSet<ListNode>.
  2. Walk the list. If adding the current node fails (it is already in the set), return it.
  3. If the walk reaches null, return null.
static ListNode hashing(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    for (ListNode cur = head; cur != null; cur = cur.next) {
        if (!visited.add(cur)) return cur;          // the walk re-enters the loop exactly at its start
    }
    return null;
}

Complexity. Time O(n): the walk takes L + C + 1 steps at most, and L + C = n. Space O(n) for the set.

This is simple and correct, but it stores every node. The follow-up asks us to drop that memory.

Approach 2: Optimal, Floyd’s algorithm with a second phase

Intuition. Phase 1 is plain loop detection: slow moves one node per step, fast moves two. If fast reaches null, there is no loop. Otherwise they meet somewhere on the circle (the gap between them shrinks by exactly one per step once both are on it, so it must hit zero).

Phase 2 finds the entrance. Put a new pointer entry on the head and move entry and slow one step at a time. They meet exactly at the start of the loop. Here is why.

Number the steps of a walk from the head: after s steps you are on node p(s). Tail nodes are visited once, so for s < L all p(s) are distinct. On the circle, p(s) = p(s') for s, s' ≥ L exactly when s - s' is a multiple of C.

So the two pointers meet for the first time exactly at the loop’s start, after L steps, without ever knowing L or C.

Algorithm.

  1. slow = fast = head. While fast and fast.next are not null, move slow by one and fast by two.
  2. If slow == fast, set entry = head and move entry and slow one step at a time until they are equal. Return entry.
  3. If the first loop ends, 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) {                         // inside the loop; now locate its entrance
            ListNode entry = head;
            while (entry != slow) {                 // head and meeting point are equally far from the start
                entry = entry.next;
                slow = slow.next;
            }
            return entry;
        }
    }
    return null;                                    // fast reached the end: no loop
}

Dry run on Example 1. Nodes n0 = 3, n1 = 2, n2 = 0, n3 = -4, with n3.next = n1. Here L = 1 and C = 3.

phase step slow fast / entry
1 1 n1 fast n2
1 2 n2 fast n1
1 3 n3 fast n3, meet after t = 3 steps
2 0 n3 entry n0
2 1 n1 entry n1, equal: return n1

The meeting happened after t = 3 steps, a multiple of C = 3, exactly as the argument predicts. Phase 2 needed L = 1 step.

Complexity. Time O(n): phase 1 ends within L + C steps of the slow pointer, and phase 2 takes L steps. Space O(1).

Edge cases and pitfalls