Why dummy nodes and two pointers
Dummy heads remove special cases at the front. Fast/slow pointers find the middle or a cycle because fast laps slow if a loop exists. Reverse is three pointers (prev, cur, next) — draw one iteration before coding.
Analogy: train cars
A linked list is a train: each car stores a coupler to the next. You can’t jump to car 50 without walking. Reverse = rehang every coupler to point backward. Fast/slow pointers = two conductors walking at different speeds to find the middle or a loop in the track.
Tools
- Dummy head for insert/delete at front
- Fast/slow for mid & cycle
- Three pointers to reverse
def reverse(head):
prev = None
while head:
nxt = head.next
head.next = prev
prev = head
head = nxt
return prevListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode nxt = head.next;
head.next = prev;
prev = head;
head = nxt;
}
return prev;
}def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next; fast = fast.next.next
if slow is fast: return True
return Falseboolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}Drill list
- Reverse list / reverse k-group
- Detect cycle + find entrance
- Merge two sorted / merge k
- Remove nth from end (two pointers)
- Reorder list
Worked trace: reverse
List 1→2→3. prev=null, cur=1. Save next=2, point 1→null, advance prev=1, cur=2. Next iter: 2→1, then 3→2. Return prev=3. Drawing one iteration prevents the usual lost-next bug.
When to reach for this pattern
Lists punish off-by-one pointer bugs more than algorithmic insight. Interviews watch whether you use a dummy, draw before/after pointers, and handle empty / single-node cases.
Core template + worked trace
Iterative reverse with a dry-run:
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def reverse_list(head: ListNode | None) -> ListNode | None:
prev, cur = None, head
while cur:
nxt = cur.next # save
cur.next = prev # flip
prev = cur # advance
cur = nxt
return prev
# 1→2→3→None
# step1: None←1 2→3 ; prev=1 cur=2
# step2: None←1←2 3 ; prev=2 cur=3
# step3: None←1←2←3 ; prev=3 cur=None → return 3class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
ListNode reverseList(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode nxt = cur.next; // save
cur.next = prev; // flip
prev = cur; // advance
cur = nxt;
}
return prev;
}
// 1→2→3→null
// step1: null←1 2→3 ; prev=1 cur=2
// step2: null←1←2 3 ; prev=2 cur=3
// step3: null←1←2←3 ; prev=3 cur=null → return 3Dummy for delete / merge so you never special-case a new head:
def remove_elements(head, val):
dummy = ListNode(0, head)
cur = dummy
while cur.next:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.nextListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0, head);
ListNode cur = dummy;
while (cur.next != null) {
if (cur.next.val == val) cur.next = cur.next.next;
else cur = cur.next;
}
return dummy.next;
}Edge cases & common bugs
Complexity — say it aloud
Interview talk track
You: ‘I’ll reverse iteratively with three pointers — prev, cur, next — so I don’t lose the rest of the list. I’ll dry-run 1→2→3 on the board, then code. Edge cases: empty and single node.’
Practice set
- Reverse Linked List
- Merge Two Sorted Lists
- Linked List Cycle / Cycle II
- Middle of the Linked List
- Remove Nth Node From End of List
- Add Two Numbers
- Reorder List
- Copy List with Random Pointer
Harder follow-up
Harder variant: Reverse Nodes in k-Group — reverse every k nodes, leave the tail if shorter than k. Count k ahead first; if not enough, stop. Same three-pointer flip inside each group; stitch with a dummy.
Pattern bank: more questions + efficient solutions
Five list staples. Draw next pointers before coding; name the three locals (prev/curr/next) or the Floyd pair aloud.
Q: Reverse Linked List — reverse a singly linked list and return the new head.
def reverse_list(head):
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
# O(n) time, O(1) spaceListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode nxt = curr.next;
curr.next = prev;
prev = curr;
curr = nxt;
}
return prev;
}
// O(n) time, O(1) spaceQ: Merge Two Sorted Lists — merge two sorted singly linked lists into one sorted list.
# assumes ListNode(val=0, next=None)
def merge_two_lists(a, b):
dummy = cur = ListNode(0)
while a and b:
if a.val <= b.val:
cur.next, a = a, a.next
else:
cur.next, b = b, b.next
cur = cur.next
cur.next = a or b
return dummy.next
# O(n+m) time, O(1) extraListNode mergeTwoLists(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0), cur = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { cur.next = a; a = a.next; }
else { cur.next = b; b = b.next; }
cur = cur.next;
}
cur.next = a != null ? a : b;
return dummy.next;
}
// O(n+m) time, O(1) extraQ: Linked List Cycle II — if a cycle exists, return the node where the cycle begins; else null (Floyd tortoise/hare).
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
return None
# O(n) time, O(1) spaceListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
// O(n) time, O(1) spaceQ: LRU Cache — implement get/put in O(1) average with capacity; evict least-recently-used on overflow (HashMap + doubly linked list).
class LRUCache:
class Node:
__slots__ = ("key", "val", "prev", "next")
def __init__(self, key=0, val=0):
self.key, self.val = key, val
self.prev = self.next = None
def __init__(self, capacity):
self.cap = capacity
self.map = {}
self.head, self.tail = self.Node(), self.Node() # sentinels
self.head.next, self.tail.prev = self.tail, self.head
def _add(self, node): # insert after head (MRU)
nxt = self.head.next
self.head.next = node
node.prev, node.next = self.head, nxt
nxt.prev = node
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def get(self, key):
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._add(node)
return node.val
def put(self, key, val):
if key in self.map:
self._remove(self.map[key])
node = self.Node(key, val)
self.map[key] = node
self._add(node)
if len(self.map) > self.cap:
lru = self.tail.prev
self._remove(lru)
del self.map[lru.key]
# O(1) get/put, O(capacity) spaceclass LRUCache {
static class Node {
int key, val; Node prev, next;
Node(int k, int v) { key = k; val = v; }
}
final int cap;
final Map<Integer, Node> map = new HashMap<>();
final Node head = new Node(0, 0), tail = new Node(0, 0);
LRUCache(int capacity) {
cap = capacity;
head.next = tail; tail.prev = head;
}
void add(Node n) {
Node nxt = head.next;
head.next = n; n.prev = head; n.next = nxt; nxt.prev = n;
}
void remove(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
int get(int key) {
if (!map.containsKey(key)) return -1;
Node n = map.get(key);
remove(n); add(n);
return n.val;
}
void put(int key, int val) {
if (map.containsKey(key)) remove(map.get(key));
Node n = new Node(key, val);
map.put(key, n); add(n);
if (map.size() > cap) {
Node lru = tail.prev;
remove(lru); map.remove(lru.key);
}
}
}
// O(1) get/put, O(capacity) spaceQ: Reverse Nodes in k-Group — reverse the list in groups of k nodes; leave the trailing < k nodes as-is.
# assumes ListNode(val=0, next=None)
def reverse_k_group(head, k):
def reverse(a, b): # reverse [a, b)
prev, curr = None, a
while curr is not b:
nxt = curr.next
curr.next = prev
prev, curr = curr, nxt
return prev
dummy = ListNode(0)
dummy.next = head
group_prev = dummy
while True:
kth = group_prev
for _ in range(k):
kth = kth.next
if not kth:
return dummy.next
group_next = kth.next
new_head = reverse(group_prev.next, group_next)
tail = group_prev.next
group_prev.next = new_head
tail.next = group_next
group_prev = tail
# O(n) time, O(1) spaceListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0, head), groupPrev = dummy;
while (true) {
ListNode kth = groupPrev;
for (int i = 0; i < k; i++) {
kth = kth.next;
if (kth == null) return dummy.next;
}
ListNode groupNext = kth.next;
ListNode prev = groupNext, curr = groupPrev.next;
while (curr != groupNext) {
ListNode nxt = curr.next;
curr.next = prev;
prev = curr;
curr = nxt;
}
ListNode tail = groupPrev.next;
groupPrev.next = kth;
groupPrev = tail;
}
}
// O(n) time, O(1) space