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.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the fast-slow pointer technique and what problems does it solve?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Two pointers advance at different speeds: slow moves 1 step, fast moves 2 steps. Floyd cycle detection: if they meet, a cycle exists. After meeting, reset slow to head and advance both 1 step at a time – they meet at the cycle entry point. Middle of linked list: when fast reaches the end (null or last node), slow is at the middle. Kth node from end: advance fast k steps first, then advance both until fast is null – slow is at the kth from end. Remove nth from end (LC 19): advance fast n+1 steps, then advance both – when fast is null, slow.next is the node to remove. All of these run in O(n) time with O(1) space, and are classic interview patterns.”}},{“@type”:”Question”,”name”:”How do you reverse a linked list iteratively and recursively?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Iterative: use three pointers prev=None, curr=head, next=None. Loop: save next = curr.next, set curr.next = prev, advance prev = curr and curr = next. Return prev (new head). O(n) time, O(1) space. Recursive: base case: if not head or not head.next, return head. Recurse on head.next to get new_head. Then head.next.next = head and head.next = None. Return new_head. O(n) time, O(n) space due to call stack. Reverse a sublist (LC 92): find the node before position left, reverse the sublist of length (right-left+1) in-place, reconnect. Use the dummy head trick to handle edge cases when left == 1.”}},{“@type”:”Question”,”name”:”How do you merge K sorted linked lists efficiently?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Min-heap approach: push the head node of each of the k lists onto a min-heap. Pop the minimum node, append it to the result list, then push that node's next (if not null) onto the heap. Total time: O(N log k) where N is total nodes and k is number of lists. Space: O(k) for the heap. Alternative: divide and conquer – pair up lists and merge pairs, reducing k lists to k/2, then k/4, etc. Total time: O(N log k), same asymptotic complexity but avoids heap overhead. The brute force approach (collect all nodes into a list, sort, rebuild) is O(N log N) – acceptable when k is large relative to N but uncommon in interviews. LC 23.”}},{“@type”:”Question”,”name”:”How do you create a deep copy of a linked list with random pointers (LC 138)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Two-pass hash map approach: first pass – create a copy of each node and store original -> copy in a hash map. Second pass – set copy.next = map[original.next] and copy.random = map[original.random]. O(n) time and space. O(1) space approach (weave): first pass – insert copy nodes between originals (1 -> 1' -> 2 -> 2' -> …). Second pass – set copy.random = original.random.next (the copy of the random target is always the next node). Third pass – unweave to separate original and copy lists. O(n) time, O(1) space but more complex and modifies the original list during processing.”}},{“@type”:”Question”,”name”:”What is the dummy head node trick and when do you use it?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Create a dummy node pointing to the head (dummy = ListNode(0); dummy.next = head). Perform operations using dummy.next instead of head. Return dummy.next as the result. This eliminates special-casing for: (1) Inserting at or before the head. (2) Deleting the head node. (3) Building a new list where the first element is determined by the loop. Without a dummy head, code needs an if-condition to set the result head vs append to an existing list. Most linked list manipulation problems (merge sorted lists, partition, remove nth from end, odd-even list) benefit from a dummy head. It costs one extra node allocation but makes code cleaner and less error-prone.”}}]}
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.