9 drills · 9 pattern exercises · 12 micro drills
Patterns used in this topic, with difficulty breakdown.
Add a new node at a specific position in a linked list.
All 9 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Add a new node at a specific position in a linked list.
In a linked list, insertion is O(1) once you're at the right spot — the cost is in walking there.
Prompt
Insert value val at position k (0-indexed) in a linked list.
Solution
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
def insert_at(head, val, k):
new = Node(val)
if k == 0:
new.next = head
return new
cur = head
for _ in range(k - 1):
cur = cur.next
# splice new node in
new.next = cur.next
cur.next = new
return head
# Test: 1->2->3, insert 9 at k=1 => 1->9->2->3In plain English: Remove the node at a specific position from a linked list.
Deletion is pointer surgery: make the previous node skip over the target by pointing to target.next.
Prompt
Delete the node at position k (0-indexed) in a linked list.
Solution
def delete_at(head, k):
if k == 0:
return head.next
cur = head
for _ in range(k - 1):
cur = cur.next
cur.next = cur.next.next # skip over target node
return head
# Test: 1->2->3->4, delete k=2 => 1->2->4In plain English: Make a linked list point backwards so the last node becomes the first.
Rewire each node to point backward by keeping three pointers — previous, current, and the saved next.
Prompt
Reverse a singly linked list in-place.
Solution
def reverse(head):
prev, cur = None, head
while cur:
nxt = cur.next # save next before rewiring
cur.next = prev
prev = cur
cur = nxt
return prev
# Test: 1->2->3->4 => 4->3->2->1In plain English: Figure out if a linked list loops back on itself instead of ending at null.
If there's a cycle, a fast pointer (2x speed) will eventually lap the slow pointer — like two runners on a circular track.
Prompt
Detect if a linked list has a cycle using O(1) space.
Solution
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# fast laps slow if cycle exists
if slow == fast:
return True
return FalseIn plain English: Find the middle element of a linked list in one pass without knowing its length.
When the fast pointer reaches the end at 2x speed, the slow pointer is exactly at the midpoint — one pass, no length needed.
Prompt
Find the middle node of a linked list.
Solution
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# fast at end = slow at middle
return slow
# Test: 1->2->3->4->5 => node(3)In plain English: Find exactly which node a linked list starts looping at.
After the pointers meet inside the cycle, the distance from head to cycle start equals the distance from the meeting point to cycle start — a property of Floyd's algorithm.
Prompt
Find the node where the cycle begins in a linked list.
Solution
def cycle_start(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = head
# equal distance to cycle start
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return NoneIn plain English: Combine two sorted linked lists into one sorted linked list.
A dummy head node eliminates edge cases for the first insertion — you just return dummy.next at the end.
Prompt
Merge two sorted linked lists into one sorted list.
Solution
def merge_sorted(a, b):
dummy = tail = Node(0) # dummy avoids empty-list edge case
while a and b:
if a.data <= b.data:
tail.next = a; a = a.next
else:
tail.next = b; b = b.next
tail = tail.next
tail.next = a or b
return dummy.next
# Test: 1->3->5 + 2->4->6 => 1->2->3->4->5->6In plain English: Clone a linked list where each node also has a random pointer to any other node in the list.
First pass: create a clone of each node and store the mapping old->new in a hash map. Second pass: wire up next and random pointers using the map. The map is the key to handling random pointers.
Prompt
A linked list has nodes with a next pointer and a random pointer (which can point to any node or null). Return a deep copy of the list.
Solution
class Node:
def __init__(self, val=0, next=None, random=None):
self.val = val
self.next = next
self.random = random
def copy_random_list(head):
if not head:
return None
old_to_new = {}
# Pass 1: create cloned nodes
cur = head
while cur:
old_to_new[cur] = Node(cur.val)
cur = cur.next
# Pass 2: set next and random pointers
cur = head
while cur:
clone = old_to_new[cur]
clone.next = old_to_new.get(cur.next)
clone.random = old_to_new.get(cur.random)
cur = cur.next
return old_to_new[head]
# Test: list 7->13->11, 13.random=7, 11.random=13
# deep copy preserves structure with new node objectsIn plain English: Build a cache with a fixed capacity. When full, evict the least recently used item. Both get and put should be O(1).
Combine a hash map (O(1) lookup) with a doubly linked list (O(1) removal and insertion). The list maintains usage order — most recent at head, least recent at tail. On access, move to head; on eviction, remove from tail.
Prompt
Design a data structure that follows the Least Recently Used (LRU) cache eviction policy. Implement get(key) and put(key, value) in O(1) time.
Solution
class DLLNode:
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.cap = capacity
self.cache = {}
self.head = DLLNode() # dummy head
self.tail = DLLNode() # dummy tail
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_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_front(node) # mark as recently used
return node.val
def put(self, key, value):
if key in self.cache:
self._remove(self.cache[key])
node = DLLNode(key, value)
self._add_front(node)
self.cache[key] = node
if len(self.cache) > self.cap:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
# Test: c = LRUCache(2)
# c.put(1,1); c.put(2,2); c.get(1) == 1
# c.put(3,3); c.get(2) == -1 (evicted)9 exercises: spot the signals, pick the method, avoid the trap.
Insert value val at position k (0-indexed) in a linked list.
Signals
Walk to node k-1, set new_node.next = node.next, node.next = new_node. O(k) time.
Trap
Don't forget the edge case: inserting at position 0 (head) needs special handling or a dummy node.
Delete the node at position k (0-indexed) in a linked list.
Signals
Walk to node k-1, set prev.next = prev.next.next. O(k) time.
Trap
Forgetting to handle deletion of the head node (k=0) or going past the end.
Reverse a singly linked list in-place.
Signals
prev/cur/next pattern: save next, point cur back to prev, advance both. O(n) time, O(1) space.
Recursive reversal: reverse the rest, then make cur.next.next = cur. Elegant but O(n) stack space.
Trap
Don't lose the reference to next_node before rewiring — save it first, then modify cur.next.
Detect if a linked list has a cycle using O(1) space.
Signals
Floyd's: slow moves 1 step, fast moves 2. If cycle exists, they meet. O(n) time, O(1) space.
Store visited nodes in a set — O(n) time but O(n) space. Violates the O(1) space constraint.
Trap
The O(1) space constraint is the key signal. Without it, hash set is fine.
Find the node where the cycle begins in a linked list.
Signals
After detection: reset slow to head, advance both by 1. They meet at cycle start. O(n).
Store each visited node; first repeat is cycle start. O(n) space.
Trap
This is a two-phase algorithm: detect first, then find start. Don't try to do both in one pass.
Find the middle node of a linked list.
Signals
Slow (1 step) and fast (2 steps). When fast hits end, slow is at the middle. One pass, O(1) space.
Trap
Counting length then iterating to n/2 works but requires two passes. Slow/fast does it in one.
Merge two sorted linked lists into one sorted list.
Signals
Compare heads of both lists, append the smaller to result. Dummy head simplifies the code. O(n+m).
Recursive merge: pick smaller head, recurse on remaining. Clean code but O(n+m) stack space.
Trap
Don't forget to append the remaining list when one is exhausted.
Deep copy a linked list where each node has a next pointer and a random pointer to any node.
Signals
First pass: map each original → clone. Second pass: set next and random using the map. O(n).
Interleave clones: A→A'→B→B'→... Set random pointers, then separate. O(1) space.
Trap
Don't forget to handle None random pointers. The hash map approach is cleaner than interleaving.
Design a data structure for Least Recently Used cache with O(1) get and put.
Signals
OrderedDict or HashMap + doubly linked list. Get moves to end. Put evicts front if over capacity. O(1).
Trap
A regular dict doesn't track access order. You need either OrderedDict or a manual DLL + HashMap.
12 quick recall drills to reinforce this topic.
Head insertion is O(1) and builds lists in reverse. Core for reverse-linked-list.
new = Node(val)
new.next = head
head = newLinear traversal is how you access linked list elements. Basis for search and length calculation.
while cur: cur = cur.nextTail insertion requires traversal to end. Know this for list construction problems.
while cur.next:
cur = cur.next
cur.next = Node(val)Dummy-head deletion avoids special-casing the head node. Essential linked list technique.
dummy = Node(0)
dummy.next = head
prev, cur = dummy, head
while cur:
if cur.val == target:
prev.next = cur.next
break
prev, cur = cur, cur.next
head = dummy.nextTwo-pass hash map maps old nodes to new clones. Second pass wires next/random.
d = {None: None}
n = head
while n:
d[n] = Node(n.val)
n = n.next
n = head
while n:
d[n].next = d[n.next]
d[n].random = d[n.random]
n = n.nextMorris-like: for each node with left child, find its inorder predecessor, link right subtree there, move left to right.
def flatten(root):
cur = root
while cur:
if cur.left:
# find rightmost of left subtree
prev = cur.left
while prev.right:
prev = prev.right
# rewire
prev.right = cur.right
cur.right = cur.left
cur.left = None
cur = cur.rightPhase 1: detect cycle with slow/fast. Phase 2: reset slow to head, advance both by 1 — they meet at cycle start.
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow # cycle startFast/slow pointer finds the middle in one pass. Core technique for merge sort on lists.
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# slow is at the middleLength calculation requires full traversal. Used as a helper in remove-nth-from-end.
length = 0
while cur:
length += 1
cur = cur.nextMerging sorted lists is the core of merge sort and merge-k-lists.
i = j = 0
merged = []
while i < len(a) and j < len(b):
if a[i] <= b[j]:
merged.append(a[i]); i += 1
else:
merged.append(b[j]); j += 1
merged.extend(a[i:])
merged.extend(b[j:])The node class is the foundation for all linked list operations. Know the constructor cold.
class Node:
def __init__(self, val, nxt=None):
self.val = val
self.next = nxtOrderedDict gives O(1) get/put with LRU eviction. Classic system design building block.
from collections import OrderedDict
class LRU:
def __init__(self, cap):
self.cap = cap
self.d = OrderedDict()
def get(self, k):
if k not in self.d: return -1
self.d.move_to_end(k)
return self.d[k]
def put(self, k, v):
self.d[k] = v
self.d.move_to_end(k)
if len(self.d) > self.cap:
self.d.popitem(last=False)