Why Linked Lists in 2025?
Linked list problems test pointer manipulation, in-place operations with O(1) space, and the two-pointer (fast/slow) technique. They appear regularly at FAANG and mid-size companies. The patterns are reusable: the fast/slow pointer pattern solves cycle detection, finding the middle, and the k-th from end. The reversal technique solves palindrome check, reverse in groups, and reorder list. Mastering ~5 patterns covers the vast majority of linked list interview questions.
Pattern 1: Fast/Slow Pointers (Floyd’s Algorithm)
Two pointers: slow moves 1 step, fast moves 2 steps. If a cycle exists, fast and slow will meet. If no cycle, fast reaches null first. Find middle: when fast reaches end, slow is at the middle (useful for palindrome check, merge sort on lists).
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
def find_cycle_start(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None # no cycle
# Reset slow to head; both move 1 step
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow # cycle start
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slowCycle start proof: if the cycle starts at distance k from head, and the cycle has length c, then when slow enters the cycle, fast is k steps ahead (modulo c). After c – (k mod c) more steps, both meet. Resetting slow to head and moving both 1 step brings them to the cycle start in k more steps.
Pattern 2: In-Place Reversal
Reverse a linked list in O(1) space: maintain prev, curr, next. Advance one node at a time, pointing curr.next backward.
def reverse_list(head):
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev # new head
def reverse_k_group(head, k):
# LC 25: Reverse Nodes in k-Group
dummy = ListNode(0, head)
group_prev = dummy
while True:
kth = get_kth(group_prev, k)
if not kth: break
group_next = kth.next
# Reverse the group
prev, curr = kth.next, group_prev.next
while curr != group_next:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
tmp = group_prev.next
group_prev.next = kth
group_prev = tmp
return dummy.next
def get_kth(curr, k):
while curr and k > 0:
curr = curr.next
k -= 1
return currPattern 3: Merge Sorted Lists and Merge Sort
Merge two sorted lists: standard merge step from merge sort. O(n+m) time, O(1) space (modify next pointers in place).
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
return dummy.next
def merge_k_lists(lists):
# LC 23: Merge k Sorted Lists — use min-heap
import heapq
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = curr = ListNode(0)
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.nextPattern 4: Reorder List and LRU Cache
Reorder List (LC 143): L0→L1→…→Ln-1→Ln to L0→Ln→L1→Ln-1→L2→…. Steps: (1) Find middle with fast/slow. (2) Reverse the second half. (3) Merge the two halves by alternating nodes. Each step is O(n), O(1) space. LRU Cache (LC 146): doubly linked list + hash map. Map: key → node (O(1) lookup). Linked list: nodes in LRU order (head = most recent, tail = least recent). Get: move node to head. Put: add to head; if capacity exceeded, remove tail. Both operations O(1). The dummy head and tail nodes simplify edge cases (no null checks on remove).
See also: Meta Interview Prep
See also: Atlassian Interview Prep
See also: Coinbase Interview Prep