Linked List Techniques
On this page
Linked list questions rarely need clever algorithms. They need careful pointer moves without losing the rest of the list. Four techniques cover nearly every interview question, and they combine: "reorder list" is find the middle, reverse the second half, then merge.
Linked Lists covers the structure itself. Here we focus on the moves.
When to recognise it
- "Reverse" a whole list, a sublist, or groups of k: three-pointer reversal.
- "Middle", "cycle", "where does the cycle start", "is it a palindrome": fast and slow pointers.
- "k-th from the end", "remove the n-th from the end": two pointers with a gap of n.
- Any change that might touch the head (delete, insert, merge, partition): a dummy node before the head.
- "Do it in O(1) extra space": you cannot copy into an array, so you must rewire pointers.
Technique 1: reverse in place
Walk the list once. At each node: save next, point the node backwards, then step forward.

class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def reverse(head):
"""Three pointers: save next, flip the link, step forward."""
prev, cur = None, head
while cur:
nxt = cur.next
cur.next = prev
prev, cur = cur, nxt
return prev
Time O(n), space O(1). The order inside the loop is the whole trick: save cur.next before overwriting it.
Technique 2: fast and slow pointers
slow moves one step, fast moves two. When fast runs off the end, slow is in the middle. If there is a cycle, fast laps slow and they meet.
def middle(head):
"""Fast/slow: when fast reaches the end, slow is in the middle (second middle for even length)."""
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
return slow
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
return True
return False
To find where a cycle starts: after they meet, move one pointer back to the head and step both one node at a time; they meet again at the cycle's entrance.
Technique 3: dummy node and a fixed gap
A dummy node in front of the head means "remove the first node" is not a special case. A gap of n between two pointers puts the trailing one right before the n-th node from the end.

def remove_nth_from_end(head, n):
"""Dummy node + gap of n: the dummy handles removing the head itself."""
dummy = ListNode(0, head)
lead = lag = dummy
for _ in range(n):
lead = lead.next
while lead.next:
lead, lag = lead.next, lag.next
lag.next = lag.next.next
return dummy.next
Technique 4: merge with a tail pointer
Building a new list is easiest with a dummy and a tail that always points at the last node:
def merge_sorted(a, b):
dummy = tail = ListNode()
while a and b:
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b
return dummy.next
Common bugs
- Losing the rest of the list by overwriting
cur.nextbefore saving it. while fast.next.nextcrashes whenfastis None. Usewhile fast and fast.next.- Returning
headafter the head moved. Returndummy.next. - Comparing values to detect a cycle. Compare nodes (
is), since values can repeat. - Off-by-one in the middle: for even lengths, the loop above returns the second middle. If you need the first one (for example, to cut the list in half), start
fastathead.next.
Say this in the interview
- "I'll use a dummy node so removing the head isn't a special case, and return dummy.next."
- "Fast moves two, slow moves one. If there's a cycle, the gap shrinks by one each step, so they must meet within one lap: O(n) time, O(1) space."
- Draw three boxes and the arrows before you code, then say each assignment as you write it.
Problems for this pattern
- Reverse Linked List: technique 1.
- Merge Two Sorted Lists: technique 4.
- Linked List Cycle: technique 2.
- Remove Nth Node From End of List: technique 3.
- Reorder List: middle, reverse, merge.
- Add Two Numbers: walk both lists with a carry and a dummy head.
- Copy List with Random Pointer: a map from old node to new node.
- LRU Cache: a doubly linked list plus a hash map.
Related
Linked Lists · Two Pointers · Heaps and Top-K (merging k lists) · Hash Maps