Linked List

Linked list problems test pointer discipline more than data-structure theory. The main risk is losing access to the rest of the list while rewiring links. Use dummy nodes, save next before mutation, and state which segment is already settled.

Quick Identifier

• Topic: linked-list
• Pattern: Pointer rewiring, dummy node, fast/slow pointers, reversal, merge, or hash plus doubly linked list.
• Core Question: Which pointer must be saved before changing next?

Quick Sights

• Typical Time Complexity: O(n) for one pass, O(n log k) when merging with a heap.
• Typical Space Complexity: O(1) for pure rewiring, O(n) when random pointers or cache maps are required.
• Core Mechanism: Preserve access to the unreprocessed suffix while building or mutating a settled prefix.

Diagram

Recognition Cues

• Reverse, reorder, remove nth, merge lists, or detect cycle.
• Need O(1) extra space with node rewiring.
• Cache design using hash map plus doubly linked list.

Problem List

Start with 206. Reverse Linked List, 021. Merge Two Sorted Lists, 019. Remove Nth From End, 141. Linked List Cycle, and 146. LRU Cache.