templates · Linked lists, sorting & selection

Fast & slow pointers

  • Find the middle of a linked list in one pass
  • "Does the list have a cycle?" or "where does the cycle start?"
  • Something keeps stepping to a next value (a list, nums[i], a digit sum) and may loop

Fast & slow pointers

the one rule

The invariant

After k steps, fast has moved exactly twice as far as slow (2k nodes against k).

write it from memory

The template

middle of the list

javajava.util.*
/** Middle node. With an even length, this returns the second of the two middles. */static ListNode middle(ListNode head) {    ListNode slow = head, fast = head;    while (fast != null && fast.next != null) {   // fast can take two steps        slow = slow.next;                         // one step        fast = fast.next.next;                    // two steps    }    return slow;}

When fast reaches the end, slow is halfway. For an even length this gives the second middle.

fill in the blanks — only these lines change per problem

  1. line 4The loop guard. Use fast.next != null && fast.next.next != null if you need the first middle (e.g. to split a list for merge sort).
  2. line 8What you do with the middle: return it, or cut the list there and reverse the second half (palindrome, reorder list).

cycle detection + cycle start

javajava.util.*
/** Where the cycle starts, or null if there is none (Floyd's algorithm). */static ListNode cycleStart(ListNode head) {    ListNode slow = head, fast = head;    while (fast != null && fast.next != null) {        slow = slow.next;        fast = fast.next.next;        if (slow == fast) {                       // they met inside the cycle            ListNode a = head;                    // one pointer back to the head            while (a != slow) {                   // same speed now: they meet at the start                a = a.next;                slow = slow.next;            }            return a;        }    }    return null;                                  // fast fell off the end: no cycle}

Once they meet, move one pointer back to the head. Both walk one step at a time, and they meet exactly where the cycle starts.

fill in the blanks — only these lines change per problem

  1. line 7The meeting check. Compare nodes with == (same object), never their values.
  2. line 16What "no cycle" means for your problem: null, false, or "the number is happy".

complexity

What it costs

time O(n)
Without a cycle, fast reaches the end in n/2 steps. With one, they meet before slow finishes one lap of the cycle, and the second phase is at most n more steps.
space O(1)
Two pointers. No HashSet of visited nodes needed.

watch out

Common bugs

  • Checking only fast != null, then calling fast.next.next. That is a NullPointerException on odd lengths, where fast lands on the last node.
  • Comparing slow.val == fast.val. Two different nodes can hold the same value.
  • Starting phase two from the meeting point with both pointers there, instead of moving one back to the head.

use it

Practise it on

learn it properly