Linked Lists Master Recap — All Patterns & Templates

Linked Lists — Master Recap

Problems 206–250 | 45 posts | Easy × 10, Medium × 25, Hard × 10

The 7 Core Patterns

All Templates

1. Reversal

def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next; curr.next = prev
        prev = curr; curr = nxt
    return prev

2. Fast/Slow — Middle

slow = fast = head
while fast and fast.next:
    slow = slow.next; fast = fast.next.next
# slow = middle (second mid for even length)

3. Fast/Slow — Cycle Detection

while fast and fast.next:
    slow = slow.next; fast = fast.next.next
    if slow is fast: # cycle!
        slow = head
        while slow is not fast:
            slow = slow.next; fast = fast.next
        return slow  # cycle start

4. N-Gap for Nth from End

dummy = ListNode(0, head)
fast = slow = dummy
for _ in range(n+1): fast = fast.next
while fast: fast = fast.next; slow = slow.next
slow.next = slow.next.next  # remove nth from end

5. Dummy Head

dummy = ListNode(0, head)
cur = dummy
# ... process ...
return dummy.next

6. Merge Two Sorted

dummy = cur = ListNode(0)
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

7. K-Group Reversal

def reverseKGroup(head, k):
    cur = head
    for _ in range(k):
        if not cur: return head
        cur = cur.next
    prev, curr = None, head
    for _ in range(k):
        nxt = curr.next; curr.next = prev; prev = curr; curr = nxt
    head.next = reverseKGroup(curr, k)
    return prev

8. LRU DLL Sentinel Pattern

class LRUCache:
    # head (LRU) <-> ... <-> tail (MRU)
    def _remove(self, node):
        node.prev.next = node.next; node.next.prev = node.prev
    def _add_tail(self, node):
        node.prev = self.tail.prev; node.next = self.tail
        self.tail.prev.next = node; self.tail.prev = node

Big O Reference

Problem Index by Pattern

Reversal

01 Reverse LL · 30 Reverse LL II · 39 Reverse K-Group · 34 Even-Length Groups

Fast/Slow Pointers

02 Middle · 03 Cycle I · 23 Cycle II · 05 Palindrome · 31 Max Twin Sum · 33 Delete Middle

Dummy Head

04 Merge Two · 10 Remove Elements · 11 Remove Nth · 18 Partition · 20 Remove Dups II

Merge / Sort

04 Merge Two · 19 Sort List · 40 Merge K · 41 Sort List O(1) Space

In-Place Pointer

13 Odd-Even · 14 Rotate · 15 Reorder · 12 Swap Pairs

Clone

21 Copy + Random Pointer

Design DLL

26 Design LL · 43 LRU Cache DLL · 44 Browser History

Floyd's on Array

24 Find Duplicate Number

MAANG Interview Priority

Must-Know (appear constantly):

• Reverse Linked List (and II, K-Group)
• Merge Two Sorted Lists
• Linked List Cycle I & II
• Remove Nth Node From End
• Merge K Sorted Lists
• LRU Cache (DLL+HashMap)

High Value Design:

• Copy List with Random Pointer (interleave trick)
• Sort List (bottom-up O(1) space)
• Find Duplicate Number (Floyd's on array)

Pattern Mastery:

• Reorder List (combines 3 patterns)
• Flatten Binary Tree to LL (Morris)
• Convert Sorted List to BST (in-order O(n))

Common Mistakes

1. Off-by-one in N-gap: Use n+1 advance, not n
2. Cycle II reset: Reset ONE pointer to head, not both
3. Reverse K-Group: Check k nodes exist BEFORE reversing
4. Dummy head tail: Always set greater.next = None in partition
5. Floyd's on array: Start both at nums[0], not index 0

Next Section → Stacks & Queues (problems 251–300)