Reverse Linked List: Iterative, Recursive, and K-Groups
Reversing a linked list (LC 206) is the foundational operation. Iterative: maintain prev=None, curr=head, advance by flipping curr.next = prev. Recursive: the base case returns the last node as the new head; on the way back up, each node’s next is reversed.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Iterative O(n) time O(1) space
def reverse_iterative(head):
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
# Recursive O(n) time O(n) space (call stack)
def reverse_recursive(head):
if not head or not head.next:
return head
new_head = reverse_recursive(head.next)
head.next.next = head
head.next = None
return new_head
# Reverse in groups of K (LC 25)
def reverse_k_group(head, k):
# check if k nodes remain
node, count = head, 0
while node and count < k:
node = node.next
count += 1
if count < k:
return head # fewer than k nodes - leave as is
# reverse k nodes
prev, curr = None, head
for _ in range(k):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# head is now tail of reversed group; connect to rest
head.next = reverse_k_group(curr, k)
return prev # prev is new head of reversed groupMerge Sorted Lists: Two-List and K-List with Heap
Merge two sorted lists (LC 21): use a dummy head and advance the smaller pointer. O(n+m) time, O(1) space. Merge K sorted lists (LC 23): naive pairwise merge is O(Nk) where N=total nodes. Use a min-heap for O(N log k) – push the head of each list, pop the smallest, push that node’s next.
import heapq
def merge_two(l1, l2):
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1; l1 = l1.next
else:
cur.next = l2; l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next
def merge_k_lists(lists):
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode(0)
cur = dummy
while heap:
val, i, node = heapq.heappop(heap)
cur.next = node
cur = cur.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.nextFind Middle and Palindrome Check
Find the middle node: slow pointer advances 1 step, fast pointer advances 2 steps. When fast reaches the end, slow is at the middle. For palindrome (LC 234): find middle, reverse the second half in-place, compare both halves node by node. Restore the list afterward if required.
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for odd length: exact middle; for even: second middle
def is_palindrome(head):
if not head or not head.next:
return True
# find middle
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# reverse second half
second = reverse_iterative(slow)
first = head
# compare
p1, p2 = first, second
result = True
while p2:
if p1.val != p2.val:
result = False
break
p1 = p1.next
p2 = p2.next
# optionally restore: reverse second half back
reverse_iterative(second)
return resultCopy List with Random Pointer
LC 138: each node has next and random pointers. Random can point to any node or null. Two approaches:
Hash map O(n) space: first pass maps original -> clone (creating all nodes). Second pass sets next and random on clones using the map.
Interleaving O(1) space: weave clones into original list (1->1′->2->2′->3->3′). Set random pointers (clone.random = orig.random.next). Separate the two lists.
class NodeWithRandom:
def __init__(self, val=0, next=None, random=None):
self.val = val; self.next = next; self.random = random
# Hash map approach - O(n) space
def copy_random_list_hashmap(head):
if not head: return None
node_map = {}
cur = head
while cur:
node_map[cur] = NodeWithRandom(cur.val)
cur = cur.next
cur = head
while cur:
if cur.next:
node_map[cur].next = node_map[cur.next]
if cur.random:
node_map[cur].random = node_map[cur.random]
cur = cur.next
return node_map[head]
# Interleaving approach - O(1) space
def copy_random_list_interleave(head):
if not head: return None
# Step 1: weave clones
cur = head
while cur:
clone = NodeWithRandom(cur.val)
clone.next = cur.next
cur.next = clone
cur = clone.next
# Step 2: set random pointers
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
# Step 3: separate lists
dummy = NodeWithRandom(0)
clone_cur = dummy
cur = head
while cur:
clone_cur.next = cur.next
cur.next = cur.next.next
clone_cur = clone_cur.next
cur = cur.next
return dummy.nextLRU Cache: Doubly Linked List + Hash Map
LC 146: get(key) and put(key, value) in O(1). Design: doubly-linked list for access order (most recent at head, least recent at tail) + hash map from key to node for O(1) lookup. On get: move node to head. On put: insert at head; if over capacity, remove tail node and delete from map.
class DLLNode:
def __init__(self, key=0, val=0):
self.key = key; self.val = val
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.cache = {} # key -> DLLNode
# dummy head (MRU side) and tail (LRU side)
self.head = DLLNode()
self.tail = DLLNode()
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 _insert_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._insert_front(node)
return node.val
def put(self, key, value):
if key in self.cache:
self._remove(self.cache[key])
node = DLLNode(key, value)
self.cache[key] = node
self._insert_front(node)
if len(self.cache) > self.cap:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
# Python shortcut using OrderedDict
from collections import OrderedDict
class LRUCacheOD:
def __init__(self, capacity):
self.cap = capacity
self.od = OrderedDict()
def get(self, key):
if key not in self.od: return -1
self.od.move_to_end(key)
return self.od[key]
def put(self, key, value):
if key in self.od:
self.od.move_to_end(key)
self.od[key] = value
if len(self.od) > self.cap:
self.od.popitem(last=False) # remove LRU (front)Flatten Multilevel Doubly Linked List
LC 430: each node may have a child pointer to another doubly linked list. Flatten so all nodes appear in pre-order: current node, then child list, then rest of current level. Iterative with explicit stack or recursive.
class MLNode:
def __init__(self, val=0, prev=None, next=None, child=None):
self.val=val; self.prev=prev; self.next=next; self.child=child
def flatten(head):
if not head: return head
cur = head
while cur:
if cur.child:
child = cur.child
nxt = cur.next
# connect cur to child
cur.next = child
child.prev = cur
cur.child = None
# find tail of child list
tail = child
while tail.next:
tail = tail.next
# connect tail to nxt
tail.next = nxt
if nxt:
nxt.prev = tail
cur = cur.next
return headInterview checklist: reverse in K-groups uses a helper that checks if K nodes exist then reverses them – practice until fluent. LRU cache is a must-know: lead with doubly-linked list + hashmap, mention OrderedDict as the shortcut. For copy with random pointer, describe both approaches and state O(1) space is preferred. Slow/fast pointer pattern (middle, cycle detection, nth-from-end) appears in multiple problems – master it as a building block.