Linked List · Fast & Slow Pointers

One-liner: you can only walk a linked list forward, so rewire next pointers carefully — and when you need the middle, the end or a loop, send a second pointer ahead at a different speed.

The analogy

Picture two runners on a running track. One jogs, one sprints at double speed. On a straight road the sprinter reaches the finish line when the jogger is exactly halfway — that is how you find the middle without knowing the length. On a circular track the sprinter eventually laps the jogger and they meet — that is how you detect a cycle without remembering every spot you passed.

Recognition signals

Reach for this pattern when you see:

1. The input is a singly linked list: no indexing, no length, no walking backwards.
2. The task is about position relative to the end (middle, n-th from the end), or about a loop.
3. A hint of O(1) extra memory, which rules out copying nodes into an array or a set.
4. The task is to change the order or links (reverse, merge, delete) rather than the values.

Step-by-step walkthrough

Find the middle of 1 → 2 → 3 → 4 → 5:

1. slow and fast both start at the head.
2. Each round: slow moves 1 step, fast moves 2.
3. Stop when fast has nothing left to jump over (fast == nil or fast.Next == nil).
4. fast travelled twice as far as slow, so slow stands in the middle.

For cycle detection the loop is the same, with one extra check each round: if they are the same node, there is a cycle. Inside a loop the gap between them shrinks by one every round, so fast cannot jump over slow.

Code template

// Template: two pointers on one list that move at different speeds.
// slow takes 1 step, fast takes 2, so when fast falls off the end, slow is at the middle;
// and if there is a cycle, fast laps slow and they must meet.
func fastSlowTemplate(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil { // guard BOTH: fast.Next.Next would panic on nil
		slow = slow.Next
		fast = fast.Next.Next
		// if slow == fast { ... they met: there is a cycle ... }
	}
	return slow // no cycle: slow is the middle
}

Why each part exists:

See it run

Floyd's cycle detection on a real list. Input format: values, a semicolon, then the index the tail points back to (-1 = no cycle). Try 1,2,3,4,5;-1 to watch fast fall off the end.

// HasCycle: Floyd's tortoise and hare.
func HasCycle(head *ListNode) bool {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast { // compare nodes (pointers), never values
			return true
		}
	}
	return false
}

The real solution

// HasCycle: Floyd's tortoise and hare.
func HasCycle(head *ListNode) bool {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast { // compare nodes (pointers), never values
			return true
		}
	}
	return false
}

More recipes

Reverse a list — flip each arrow, but save next first or you lose the rest of the list:

// ReverseList: flip every Next pointer in place.
func ReverseList(head *ListNode) *ListNode {
	var prev *ListNode
	for cur := head; cur != nil; {
		next := cur.Next // save it, or we lose the rest of the list
		cur.Next = prev  // flip the arrow
		prev, cur = cur, next
	}
	return prev
}

Merge two sorted lists — dummy node plus a moving tail:

// MergeTwoLists: splice two sorted lists into one.
// The dummy node removes the "which node is the head?" special case.
func MergeTwoLists(a, b *ListNode) *ListNode {
	dummy := &ListNode{}
	tail := dummy
	for a != nil && b != nil {
		if a.Val <= b.Val { // <= keeps the merge stable
			tail.Next, a = a, a.Next
		} else {
			tail.Next, b = b, b.Next
		}
		tail = tail.Next
	}
	if a != nil {
		tail.Next = a // at most one list has leftovers: attach it whole
	} else {
		tail.Next = b
	}
	return dummy.Next
}

Middle of the list — the template, returning slow:

// MiddleNode: second middle for even length.
func MiddleNode(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

Where the cycle starts — after the meeting point, restart one pointer at the head and move both one step at a time; they meet at the entrance. (Why it works: if the head-to-entrance distance is a, then at the meeting point fast has travelled exactly one or more full laps more than slow, so walking a steps from the meeting point lands on the entrance too.)

// DetectCycle: the node where the cycle begins, or nil.
// After they meet, restart one pointer at head; moving both one step at a time,
// they meet again exactly at the cycle entrance.
func DetectCycle(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			for p := head; p != slow; { // distance head->entrance == distance meeting->entrance
				p, slow = p.Next, slow.Next
			}
			return slow
		}
	}
	return nil
}

Remove the n-th node from the end — give fast a head start of n, then move both until fast is on the last node:

// RemoveNthFromEnd: remove the nth node from the end in one pass.
// fast gets an n-step head start, so when fast reaches the end, slow is just before the target.
func RemoveNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{Next: head} // lets us delete the real head without a special case
	fast, slow := dummy, dummy
	for i := 0; i < n && fast != nil; i++ {
		fast = fast.Next
	}
	if fast == nil { // n is larger than the list: nothing to remove
		return head
	}
	for fast.Next != nil {
		fast, slow = fast.Next, slow.Next
	}
	slow.Next = slow.Next.Next
	return dummy.Next
}

Complexity

In a cycle of length c, fast closes the gap by one node per round, so it catches slow within about n rounds: still linear.

Common mistakes

Practice ladder

Ordered Easy → Hard. Before coding, decide what each pointer is for and where a dummy node would help.

1. 1.
   Reverse Linked List

   Three names: where you came from, where you are, where you go next.
   Easy
2. 2.
   Merge Two Sorted Lists

   A placeholder head saves the first-node special case.
   Easy
3. 3.
   Middle of the Linked List
   Easy
4. 4.
   Linked List Cycle

   Do it without extra memory.
   Easy
5. 5.
   Remove Nth Node From End of List

   Make a fixed gap between two pointers.
   Medium
6. 6.
   Linked List Cycle II

   What does restarting one pointer from the head tell you?
   Medium
7. 7.
   Reorder List

   Three earlier problems combined: split, flip one half, interleave.
   Medium
8. 8.
   Reverse Nodes in k-Group

   Reverse in chunks, and reconnect each chunk to its neighbours.
   Hard
9. 9.
   Merge k Sorted Lists

   Merging two is easy; which structure picks the smallest of k fronts?
   Hard

Which pattern? Drills

Unlabeled problems — pick the pattern, then read why.