Linked List Cycle

The problem

head is the first node of a linked list, or null for an empty list. A node holds a value, val, and a link, next, to the node after it. Normally the last node's next is null. If it instead points back at a node of the list, even the last node itself, following next never ends: the list has a cycle. Return true if the list has a cycle and false if it has none. An empty list has none. Values may repeat. The examples give values, the node values, and pos, the index the last node links back to, or -1 for none. Your function gets only head.

What to write

Implement solve using the node objects described above. The judge constructs the objects from the serialized examples.

type ListNode = {val:number;next:ListNode|null};

function solve(head: ListNode | null): boolean

Input
values = [3,2,0,-4]
pos = 1

Output
true

Input
values = [1,2]
pos = 0

Output
true

Constraints

0 ≤ node count ≤ 10000.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The list can hold 10,000 nodes. In a list with a cycle no next is ever null, so walking until you find null never ends. Equal values prove nothing either, because different nodes may hold the same value. What counts is being on the very same node again.

2. Hint 2: Ask a smaller question

   Draw 1 → 2 → 3 → 4, with 4 linking back to 2. Keep one finger on node 1 and walk a pencil along the links. Does the pencil ever come back to your finger? What would the finger have to do so that the pencil is sure to reach it?

3. Hint 3: Name the pattern

   Use two pointers, variables that each hold one node. Move one a single node per round and the other two. On a list with an end the fast one runs out of nodes. In a cycle it comes round and lands on the slow one. A chain of links that may loop back signals fast and slow pointers. Read the lesson on fast and slow pointers.

4. Hint 4: State the invariant

   After every round the fast pointer has moved exactly twice as many nodes as the slow one. On a list with an end, this keeps the fast pointer strictly ahead until it runs out of nodes. Inside a cycle the fast pointer gains one node on the slow one per round, so the gap between them closes.

5. Hint 5: Sketch the pseudocode

   slow = head, fast = head. While fast is a node and the node after fast exists: move slow one node on and fast two nodes on; if slow and fast are now the same node, return true. When the loop ends, return false.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Advance one pointer one step and another two steps. They meet exactly when a cycle exists.

The slow way

Walk the list and keep every node you pass in a set. Arriving at a node that is already in the set means there is a cycle, and reaching the end means there is none. It is correct and takes one pass, but the set grows until it holds every node of the list: O(n) extra memory.

The insight

Send two pointers, variables that each hold one node, down the list at different speeds. On a list with an end, the fast one reaches the end first. In a cycle neither can leave, and the fast one closes in on the slow one by one node per round, so sooner or later both are on the same node.

Step by step

1. Start a slow pointer and a fast pointer on the head. Both pointers begin on the first node, or on nothing if the list is empty. These two variables are all the memory the method needs.
2. Continue while the fast pointer has not run out of nodes. Moving two nodes on needs the node the fast pointer is on and the node after it. If either is missing, the list has an end, and a list with an end has no cycle.
3. Move the slow pointer one node and the fast pointer two. The difference in speed does the work. Each round the fast pointer gets one node further ahead of the slow one, or, inside a cycle, one node closer to it from behind.
4. If both pointers are on the same node, there is a cycle. On a list with an end the fast pointer is strictly ahead after every move. So the two can share a node only after the fast one has come round a cycle. Compare the nodes themselves, not their values.
5. The fast pointer reached the end, so there is no cycle. In a list with a cycle every node has a node after it, so the fast pointer could never run out. Running out of nodes proves that the list ends.

The same numbered steps are the comments in each solution.

function solve(head) {
  // 1. Start a slow pointer and a fast pointer on the head
  let slow = head,
    fast = head;
  // 2. Continue while the fast pointer has not run out of nodes
  while (fast?.next) {
    // 3. Move the slow pointer one node and the fast pointer two
    slow = slow.next;
    fast = fast.next.next;
    // 4. If both pointers are on the same node, there is a cycle
    if (slow === fast) return true;
  }
  // 5. The fast pointer reached the end, so there is no cycle
  return false;
}

type ListNode = { val: number; next: ListNode | null };
function solve(head: ListNode | null): boolean {
  // 1. Start a slow pointer and a fast pointer on the head
  let slow = head,
    fast = head;
  // 2. Continue while the fast pointer has not run out of nodes
  while (fast?.next) {
    // 3. Move the slow pointer one node and the fast pointer two
    slow = slow!.next;
    fast = fast.next.next;
    // 4. If both pointers are on the same node, there is a cycle
    if (slow === fast) return true;
  }
  // 5. The fast pointer reached the end, so there is no cycle
  return false;
}

def solve(head):
    # 1. Start a slow pointer and a fast pointer on the head
    slow = fast = head
    # 2. Continue while the fast pointer has not run out of nodes
    while fast and fast.next:
        # 3. Move the slow pointer one node and the fast pointer two
        slow = slow.next
        fast = fast.next.next
        # 4. If both pointers are on the same node, there is a cycle
        if slow is fast:
            return True
    # 5. The fast pointer reached the end, so there is no cycle
    return False

Example 1, traced

Input
values = [3,2,0,-4]
pos = 1

Output
true

Why it works

If the list has an end, the fast pointer moves further ahead of the slow one every round until the fast pointer runs out of nodes, so the answer is false. If the list has a cycle, both pointers end up inside the cycle. From then on the fast pointer is one node closer behind the slow one after each round, so they must land on the same node.

Time and space

Time O(n), extra space O(1). Without a cycle the fast pointer reaches the end after about n / 2 rounds. With a cycle the two pointers meet within n rounds, because the gap closes by one node each round. Either way the time is O(n). Only two pointers are stored, so the space is O(1).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Compare the nodes themselves, not their values. Different nodes may hold equal values: for the list 4, 1, 1, 1, 2, 4, 1, which has no cycle, a comparison of values answers true after the first round.
• Check that the fast pointer and the node after it both exist before moving it two nodes. Without the check, a list with an end makes the program read next of nothing, and it stops with an error.
• Compare after moving, not before. Both pointers start on the head, so a comparison made first finds them equal at once and answers true for every list of two or more nodes.

Pattern

Fast and slow pointers. Builds on Reorder List.

Keep going