Linked list problems trip up candidates because pointer manipulation is easy to mess up under pressure. These patterns cover every common linked list interview question.
ListNode Definition and Basic Operations
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build a list from array (useful for testing)
def build_list(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
# Convert list back to array
def to_array(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
Fast-Slow Pointer
Two pointers moving at different speeds. Fast moves 2 steps per iteration, slow moves 1. When fast reaches the end, slow is at the middle.
# Detect cycle (Floyd's algorithm)
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# Find cycle start
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
# Move one pointer to head, advance both at speed 1
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None
# Find middle of list
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # For even-length lists, returns second middle node
# Find kth node from end (k=1 means last node)
def kth_from_end(head, k):
fast = slow = head
for _ in range(k):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
return slow
Reverse a Linked List
LC 206. The iterative approach with three pointers is the most reliable in an interview.
# Iterative - O(n) time O(1) space
def reverse_list(head):
prev = None
curr = head
while curr:
next_node = curr.next # save before breaking link
curr.next = prev # reverse the link
prev = curr # advance prev
curr = next_node # advance curr
return prev
# Recursive
def reverse_list_recursive(head):
if not head or not head.next:
return head
new_head = reverse_list_recursive(head.next)
head.next.next = head
head.next = None
return new_head
# Reverse a sublist from position left to right (LC 92)
def reverse_between(head, left, right):
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.next
Merge Two Sorted Lists
LC 21. The dummy head trick eliminates the special case of an empty result list.
def merge_two_lists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2 # attach remaining
return dummy.next
Always use a dummy head when building a new list or when the head node might change. Return dummy.next as the result.
Merge K Sorted Lists
LC 23. Two approaches: min-heap (simpler to implement) or divide-and-conquer.
import heapq
# Min-heap approach - O(N log k) where N = total nodes, k = number of lists
def merge_k_lists(lists):
dummy = ListNode(0)
curr = dummy
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
while heap:
val, i, node = heapq.heappop(heap)
curr.next = node
curr = curr.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
# Divide and conquer - repeatedly merge pairs of lists
def merge_k_lists_dc(lists):
if not lists:
return None
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i + 1] if i + 1 < len(lists) else None
merged.append(merge_two_lists(l1, l2))
lists = merged
return lists[0]
The heap approach needs a tiebreaker (the index i) because Python compares tuple elements in order and ListNode doesn’t support comparison.
Reorder List
LC 143: reorder L0 -> Ln -> L1 -> Ln-1 -> L2 -> … Three steps: find middle, reverse second half, merge two halves.
def reorder_list(head):
if not head or not head.next:
return
# Step 1: find middle
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Step 2: reverse second half
second = slow.next
slow.next = None # cut the list
prev = None
while second:
tmp = second.next
second.next = prev
prev = second
second = tmp
second = prev
# Step 3: merge first and reversed second halves
first = head
while second:
tmp1 = first.next
tmp2 = second.next
first.next = second
second.next = tmp1
first = tmp1
second = tmp2
Deep Copy with Random Pointers
LC 138: copy a linked list where each node has a next and a random pointer.
class Node:
def __init__(self, val, next=None, random=None):
self.val = val
self.next = next
self.random = random
# Two-pass with hash map - O(n) time O(n) space
def copy_random_list(head):
if not head:
return None
old_to_new = {}
curr = head
# First pass: create all new nodes
while curr:
old_to_new[curr] = Node(curr.val)
curr = curr.next
# Second pass: wire up next and random pointers
curr = head
while curr:
if curr.next:
old_to_new[curr].next = old_to_new[curr.next]
if curr.random:
old_to_new[curr].random = old_to_new[curr.random]
curr = curr.next
return old_to_new[head]
# O(1) space weave approach: interleave copied nodes with originals
def copy_random_list_o1(head):
if not head:
return None
# Step 1: insert copy after each original node
curr = head
while curr:
copy = Node(curr.val)
copy.next = curr.next
curr.next = copy
curr = copy.next
# Step 2: set random pointers on copies
curr = head
while curr:
if curr.random:
curr.next.random = curr.random.next
curr = curr.next.next
# Step 3: separate the two lists
dummy = Node(0)
copy_curr = dummy
curr = head
while curr:
copy_curr.next = curr.next
curr.next = curr.next.next
copy_curr = copy_curr.next
curr = curr.next
return dummy.next
LRU Cache with Doubly Linked List
O(1) get and put using a hash map plus doubly linked list. The list maintains access order; hash map gives O(1) node lookup.
class DLinkedNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {}
# Dummy head and tail avoid edge cases
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_front(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._add_to_front(node)
return node.val
def put(self, key, value):
if key in self.cache:
self._remove(self.cache[key])
node = DLinkedNode(key, value)
self.cache[key] = node
self._add_to_front(node)
if len(self.cache) > self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
Common Pitfalls
- Null check before .next: Always verify a node is not None before accessing .next. Pattern:
while curr and curr.next - Losing track of nodes when relinking: Save next_node = curr.next before changing curr.next. Draw the state before writing code.
- Off-by-one in position problems: Decide if positions are 0-indexed or 1-indexed upfront. LC problems usually use 1-indexed.
- Forgetting to terminate the list: After splitting or reversing, set the tail’s .next to None to avoid cycles in the result.
- Modifying head node: Use a dummy head when the result list might start at a different node than the input.
Pattern: Dummy Head Node
The dummy head node is the single most useful linked list trick. It eliminates all special cases for operations at the head of the list.
# Remove all nodes with value val (LC 203)
def remove_elements(head, val):
dummy = ListNode(0, head)
curr = dummy
while curr.next:
if curr.next.val == val:
curr.next = curr.next.next # skip the node
else:
curr = curr.next
return dummy.next # never need to check if head changed
Use a dummy head whenever: you might delete the head node, you are building a new list from scratch, or the head of the result depends on the algorithm’s logic.
Meta coding interviews frequently test linked list manipulation. See common patterns for Meta interview: linked list problems.
Uber coding rounds include linked list and pointer manipulation. See patterns for Uber interview: linked list and pointer problems.
Atlassian coding rounds include linked list problems. See patterns for Atlassian interview: linked list and data structure problems.