Linked Lists: Pointers, Patterns & Pitfalls
Master singly and doubly linked lists — insertion, deletion, reversal, cycle detection, and the fast/slow pointer technique that solves countless problems.
Why Linked Lists Still Matter
Linked lists provide O(1) insertion and deletion at any position (given a reference), unlike arrays which require O(n) shifting. They're the foundation for stacks, queues, hash table chaining, LRU caches, and adjacency lists. More importantly, linked list problems test your ability to manipulate pointers — a skill that transfers to trees, graphs, and system design.
class ListNode:
def __init__(self, val: int = 0, next: "ListNode | None" = None):
self.val = val
self.next = next
def __repr__(self):
vals = []
node = self
while node:
vals.append(str(node.val))
node = node.next
return " -> ".join(vals)Pattern: Dummy Head Node
Many linked list problems require special handling for the head node. A dummy node eliminates edge cases by providing a consistent 'previous' node. Create a dummy, build the result after it, and return dummy.next.
def merge_two_sorted(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
"""Merge two sorted linked lists into one sorted list."""
dummy = ListNode(0)
current = dummy
while l1 and l2:
if l1.val <= l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 or l2
return dummy.nextPattern: Fast & Slow Pointers
The tortoise-and-hare technique uses two pointers moving at different speeds. The slow pointer moves one step, the fast moves two. When fast reaches the end, slow is at the middle. If there's a cycle, they'll eventually meet. This pattern solves middle-finding, cycle detection, and palindrome checking.
def find_middle(head: ListNode | None) -> ListNode | None:
"""Find the middle node of a linked list."""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def has_cycle(head: ListNode | None) -> bool:
"""Detect if a linked list has a cycle (Floyd's algorithm)."""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
def find_cycle_start(head: ListNode | None) -> ListNode | None:
"""Find where the cycle begins (if any)."""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
# Reset one pointer to head, move both at speed 1
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return NoneFloyd's cycle detection is O(n) time, O(1) space. The math behind why resetting one pointer to head finds the cycle start: if the cycle begins at position k, both pointers will meet at exactly position k after the reset.
Pattern: In-Place Reversal
Reversing a linked list is a fundamental operation. The iterative approach uses three pointers (prev, curr, next) and runs in O(n) time, O(1) space. This technique extends to reversing sublists, k-group reversal, and reorder problems.
def reverse_list(head: ListNode | None) -> ListNode | None:
"""Reverse a singly linked list in-place."""
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
def reverse_between(head: ListNode | None, left: int, right: int) -> ListNode | None:
"""Reverse nodes from position left to right (1-indexed)."""
dummy = ListNode(0, head)
prev = dummy
for _ in range(left - 1):
prev = prev.next
curr = prev.next
for _ in range(right - left):
next_node = curr.next
curr.next = next_node.next
next_node.next = prev.next
prev.next = next_node
return dummy.nextAlways draw out pointer changes on paper before coding. The most common bug is losing a reference — save next before modifying curr.next.