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 Listprev, curr, next 3 pointerseasy
- 2.Middle of the Linked Listslow + fast (1x, 2x)easy
- 3.Linked List CycleFloyd Cycle Detection (slow == fast)easy
- 4.Linked List Cycle IIFind cycle start nodemedium
- 5.Merge Two Sorted ListsDummy head + 2 pointerseasy
- 6.Remove Nth Node From End of ListTwo pointers with gap Nmedium
- 7.Palindrome Linked ListFind mid + reverse second halfeasy
- 8.Intersection of Two Linked ListsTwo pointers reset to opposite headseasy
- 9.Add Two NumbersDummy node + carry additionmedium
- 10.Reorder ListFind mid + reverse + interleavemedium
- 11.Swap Nodes in PairsDummy head + pointer reconnectionmedium
- 12.Reverse Linked List IISub-list pointer reversal [left..right]medium
- 13.Reverse Nodes in K-GroupReverse in groups of Khard
- 14.Copy List with Random PointerHash map or interleave nodesmedium
- 15.Sort ListMerge sort (find mid + merge)medium
Also Important
10 more questions worth practicing.
- 16.Remove Linked List ElementsDummy head + pointer skipeasy
- 17.Delete Node in a Linked ListCopy next value into current nodemedium
- 18.Odd Even Linked ListSeparate odd/even list headsmedium
- 19.Partition ListTwo dummy lists (< x and >= x)medium
- 20.Rotate ListMake ring + cut at (length - k % length)medium
- 21.Remove Duplicates from Sorted ListSkip identical next valueseasy
- 22.Remove Duplicates from Sorted List IIDummy head + skip all duplicatesmedium
- 23.Merge K Sorted ListsMin Heap / Divide & Conquer Mergehard
- 24.Flatten a Multilevel Doubly Linked ListStack / Recursive DFSmedium
- 25.LRU CacheHashMap + 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."
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
[1] โ [2] โ [3] โ nilEach node knows only next. Lower memory usage per node.
nil โ [1] โ [2] โ [3] โ nilEach node knows both prev and next. Enables O(1) removals (e.g. LRU Cache).
Common Interview Mistakes
Reconnecting curr.Next = prev BEFORE saving next = curr.Next causes loss of the remaining nodes!
Accessing fast.Next.Next without checking if fast != nil and fast.Next != nil first.
Returning original head after reversing or modifying the list instead of returning prev or dummy.Next.
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.Nextfirst. - Rule 4: Use a dummy node when head may change.
- Rule 5:
slow + fastis 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."