Linked List Summary (Dummy Nodes, Pitfalls, Complexity)
easy-mediumLinked ListDesign PatternsSummary
Dummy Node (Sentinel Node) Pattern
Almost every problem that modifies a linked list should use a dummy node. Reasons include:
- The head node might be deleted or replaced.
- It eliminates many redundant
nullchecks.
ListNode dummy = new ListNode(0, head);
// ... perform operations ...
return dummy.next; // Returns the actual new head
Common Pitfalls
1. Forgetting to Truncate the Tail
If you are re-partitioning a list (e.g., A → B → C → D), and nodes A and C end up in a new list, B might still point to C, creating an unintentional cycle or junk data.
// ERROR: Forgetting to truncate the tail of the 'greater' list segment
ListNode greater = new ListNode(0);
// ... operations ...
greaterTail.next = null; // CRITICAL: Prevent cycles!
2. Null Check Order in Loops
// CORRECT: Check 'fast' first, then 'fast.next'
while (fast != null && fast.next != null) { ... }
// INCORRECT: Might throw NullPointerException if 'fast' is null
while (fast.next != null && fast != null) { ... }
3. Modifying Head Directly Without Saving
// ERROR: 'head' is moved to the end, lost forever
while (head != null) {
head = head.next;
}
// CORRECT: Use a temporary pointer
ListNode cur = head;
while (cur != null) {
cur = cur.next;
}
Technique Summary Table
| Technique | Common Scenarios |
|---|---|
| Dummy Node | Situations where the head might change or be removed. |
| Fast & Slow Pointers | Midpoint finding, cycle detection, K-th from end. |
| Recursion | Divide and Conquer (Merge Sort), Reversal logic. |
| Two-Pass Approach | Finding length first, then operating relative to length. |
| Stack | Reversing order (e.g., Add Two Numbers II). |
Linked List vs. Array
| Operation | Linked List | Array |
|---|---|---|
| Random Access | O(n) | O(1) |
| Head Insertion/Deletion | O(1) | O(n) |
| Mid Insertion/Deletion | O(1) (given predecessor) | O(n) |
| Space | Extra per-node pointer overhead | Contiguous memory |
| Cache Friendliness | Poor (scattered addresses) | Good (spatial locality) |
Essential Linked List Problem Checklist
Fundamentals:
✅ 206 Reverse Linked List
✅ 92 Reverse Linked List II
✅ 25 Reverse Nodes in k-Group
✅ 24 Swap Nodes in Pairs
Two Pointers:
✅ 876 Middle of the Linked List
✅ 141 Linked List Cycle I
✅ 142 Linked List Cycle II
✅ 160 Intersection of Two Linked Lists
✅ 19 Remove N-th Node From End of List
Merging & Sorting:
✅ 21 Merge Two Sorted Lists
✅ 23 Merge K Sorted Lists
✅ 148 Sort List
Advanced Applications:
✅ 2 Add Two Numbers
✅ 445 Add Two Numbers II
✅ 234 Palindrome Linked List
✅ 138 Copy List with Random Pointer
✅ 143 Reorder List
✅ 146 LRU Cache
✅ 460 LFU Cache