Pattern #13

Linked List

Important interview questions, thinking patterns, node pointer manipulations, and rules for solving linked list problems in Go.

Must Solve

15 core questions — solve these first.

1.Reverse Linked List
prev, curr, next 3 pointerseasy
2.Middle of the Linked List
slow + fast (1x, 2x)easy
3.Linked List Cycle
Floyd Cycle Detection (slow == fast)easy
4.Linked List Cycle II
Find cycle start nodemedium
5.Merge Two Sorted Lists
Dummy head + 2 pointerseasy
6.Remove Nth Node From End of List
Two pointers with gap Nmedium
7.Palindrome Linked List
Find mid + reverse second halfeasy
8.Intersection of Two Linked Lists
Two pointers reset to opposite headseasy
9.Add Two Numbers
Dummy node + carry additionmedium
10.Reorder List
Find mid + reverse + interleavemedium
11.Swap Nodes in Pairs
Dummy head + pointer reconnectionmedium
12.Reverse Linked List II
Sub-list pointer reversal [left..right]medium
13.Reverse Nodes in K-Group
Reverse in groups of Khard
14.Copy List with Random Pointer
Hash map or interleave nodesmedium
15.Sort List
Merge sort (find mid + merge)medium

Also Important

10 more questions worth practicing.

16.Remove Linked List Elements
Dummy head + pointer skipeasy
17.Delete Node in a Linked List
Copy next value into current nodemedium
18.Odd Even Linked List
Separate odd/even list headsmedium
19.Partition List
Two dummy lists (< x and >= x)medium
20.Rotate List
Make ring + cut at (length - k % length)medium
21.Remove Duplicates from Sorted List
Skip identical next valueseasy
22.Remove Duplicates from Sorted List II
Dummy head + skip all duplicatesmedium
23.Merge K Sorted Lists
Min Heap / Divide & Conquer Mergehard
24.Flatten a Multilevel Doubly Linked List
Stack / Recursive DFSmedium
25.LRU Cache
HashMap + Doubly Linked Listmedium

How to Think

Need reverse?prev, curr, next
Need middle?slow + fast
Need cycle?slow + fast (if they meet: cycle exists)
Need nth node from end?two pointers with gap
Need merge sorted lists?pointer on list A, pointer on list B
Need change head safely?dummy node
Need reconnect nodes?Always save next before changing links

Go Node Struct & Templates

ListNode Definition & Traversal

type ListNode struct {
    Val  int
    Next *ListNode
}

// Basic Traversal
curr := head
for curr != nil {
    curr = curr.Next
}

Reverse Linked List Template

var prev *ListNode
curr := head

for curr != nil {
    next := curr.Next // 1. Save next
    curr.Next = prev  // 2. Reverse link
    prev = curr       // 3. Move prev forward
    curr = next       // 4. Move curr forward
}
return prev // New head

👉 Time: O(n) | Space: O(1)

The Dummy Node Pattern

Without a dummy node, operations that modify the head (like removing the first node, merging lists, or partitioning) require annoying special-case conditional logic.

dummy := &ListNode{Next: head}
curr := dummy

// Perform operations safely...

return dummy.Next // Returns updated head clean & safe!

💡 Golden Rule: "Dummy node removes annoying head edge cases."

Visual Memory Rule

prev   curr   next
 ↓      ↓      ↓
nil ← [1]    [2] → [3]

1. save next
2. curr.Next = prev
3. prev = curr
4. curr = next

💡 Golden Rule: "In Linked List problems, draw the pointers first — then change the links."

Singly vs Doubly Linked List

Singly Linked List

[1] → [2] → [3] → nil

Each node knows only next. Lower memory usage per node.

Doubly Linked List

nil ← [1] ⇄ [2] ⇄ [3] → nil

Each node knows both prev and next. Enables O(1) removals (e.g. LRU Cache).

Common Interview Mistakes

1. Losing the List

Reconnecting curr.Next = prev BEFORE saving next = curr.Next causes loss of the remaining nodes!

2. Nil Pointer Crash

Accessing fast.Next.Next without checking if fast != nil and fast.Next != nil first.

3. Forgetting Head Can Change

Returning original head after reversing or modifying the list instead of returning prev or dummy.Next.

4. Cycle Infinite Loop

Standard for curr != nil loop never terminates if a cycle exists. Use slow + fast pointers.

Interview Rules

1. Reverse list? → prev, curr, next
2. Find middle? → slow + fast (1x, 2x)
3. Detect cycle? → slow + fast
4. Nth from end? → two pointers with gap N
5. Merge sorted lists? → two list pointers
6. Head may change? → dummy node (dummy.Next = head)
7. Delete node? → reconnect links (prev.Next = curr.Next)
8. Always save next before changing pointers
9. Traversal cost → O(n)
10. Known-node insert/delete → O(1)

Small Rules

Rule 1: Access by index is O(n) for Linked List vs O(1) for Array.
Rule 2: Insert/delete when node pointer is known is O(1).
Rule 3: Never lose the rest of the list — save next := curr.Next first.
Rule 4: Use a dummy node when head may change.
Rule 5: slow + fast is used for middle, cycle, cycle start, palindrome, and nth from end.

Production Thinking

LRU Cache → HashMap (O(1) lookup) + Doubly Linked List (O(1) move to front)

Job Queue → Linked nodes Job A → Job B → Job C for cheap insertions/removals

Browser History → previous ← current → next (Doubly linked navigation)

Undo / Redo → Doubly linked state timeline

Memory Trade-Off → Each node uses extra memory for pointer(s) vs contiguous array

Remember This

Reverse                     → prev + curr + next
Middle                      → slow + fast
Cycle                       → slow + fast
Nth from end                → pointer gap
Merge lists                 → two pointers
Head edge case              → dummy node
Changing link               → save next first
Known-node insert/delete    → O(1)

💡 Golden Rule: "In Linked List problems, draw the pointers first — then change the links."