Linked list problems test pointer manipulation skills and appear in approximately 15% of coding interviews. The key to solving them efficiently is recognizing the pattern and applying the right technique. This guide covers the essential linked list patterns — reversal, merging, cycle detection, and dummy node tricks — that appear most frequently at top tech companies.
Linked List Fundamentals
A singly linked list: each node has a value and a next pointer. No random access — must traverse from the head to reach any node. Insert at head: O(1). Insert at tail: O(N) without a tail pointer, O(1) with one. Delete by value: O(N) (search + unlink). Search: O(N). A doubly linked list adds a prev pointer, enabling O(1) delete when you have a reference to the node (used in LRU cache). Interview tip: draw the linked list on paper. Track every pointer change. Off-by-one errors and lost references are the most common bugs. Use the dummy node technique to simplify edge cases (empty list, single element, head changes).
Pattern 1: Reversal
Reverse a linked list: iterate through the list, for each node change its next pointer to point to the previous node. Three pointers: prev (starts null), curr (starts at head), next (saves curr.next before overwriting). Loop: next = curr.next, curr.next = prev, prev = curr, curr = next. When curr is null, prev is the new head. Time: O(N), Space: O(1). Recursive reversal: reverse the rest of the list (recurse on head.next), then make head.next.next = head (the reversed tail points back to head), head.next = null. Time: O(N), Space: O(N) stack. Partial reversal: reverse nodes between positions left and right (LeetCode 92). Use a pointer to reach position left-1, reverse the sublist from left to right, reconnect the reversed sublist. Reverse in K-groups: reverse every K nodes. If remaining nodes are fewer than K, leave them as-is. Use the basic reversal on each group of K nodes, then connect the groups. This problem combines reversal with careful pointer bookkeeping.
Pattern 2: Fast-Slow Pointer
Two pointers moving at different speeds solve several linked list problems: (1) Find the middle: slow moves 1 step, fast moves 2 steps. When fast reaches the end, slow is at the middle. For even-length lists, slow lands on the second middle node. To get the first middle, check fast.next.next instead of fast.next. (2) Cycle detection (Floyd): slow moves 1, fast moves 2. If they meet, there is a cycle. If fast reaches null, no cycle. To find the cycle start: after meeting, move one pointer to head, advance both at speed 1 — they meet at the cycle start. (3) Nth node from end: advance fast by N steps first, then advance both at speed 1. When fast reaches null, slow is at the Nth node from the end. For deletion, keep a reference to slow.prev or use a dummy node. (4) Palindrome check: find the middle (fast-slow), reverse the second half, compare with the first half, then reverse the second half back to restore the original list. These problems all share the technique of using speed difference to create a useful positional relationship between two pointers.
Pattern 3: Merge
Merge two sorted linked lists: use a dummy node as the start of the merged list. Compare the heads of both lists, append the smaller one to the merged list, advance that list pointer. When one list is exhausted, append the rest of the other. Time: O(N + M). The dummy node avoids special-casing the first element. Merge K sorted lists: (1) Priority queue approach — add the head of each list to a min-heap. Extract-min gives the smallest element. Add the next element from that list to the heap. Time: O(N * log K) where N is total elements and K is lists. (2) Divide and conquer — merge lists pairwise: merge list 1 with list 2, merge list 3 with list 4, etc. Then merge the results pairwise. Like merge sort on the lists. Time: O(N * log K). Sort a linked list: merge sort is ideal for linked lists (no random access needed, and the merge step is natural for linked lists). Split the list at the middle (fast-slow pointer), recursively sort each half, merge the sorted halves. Time: O(N log N), Space: O(log N) for recursion stack.
Pattern 4: Dummy Node and Edge Cases
The dummy node technique: create a dummy node before the head. Set dummy.next = head. Operate on the list. Return dummy.next as the new head. This eliminates edge cases where the head itself changes (deletion of head, insertion before head, empty list). Example: remove all nodes with value V. Without dummy: special-case if head.val == V. With dummy: iterate from dummy, if curr.next.val == V then curr.next = curr.next.next. The head change is handled automatically. Partition list: given a value X, rearrange so nodes less than X come before nodes >= X. Create two dummy nodes (before_head, after_head). Iterate: append each node to the appropriate list. Connect before_tail.next = after_head.next. Return before_head.next. Reorder list: given 1->2->3->4->5, reorder to 1->5->2->4->3. Three steps: find the middle (fast-slow), reverse the second half, merge alternating nodes from both halves. Common edge cases to always check: empty list (head is null), single node, two nodes, and even vs odd length.
Pattern 5: Copy and Reconstruct
Copy list with random pointer: each node has next and random pointers. Deep copy the list preserving both pointer structures. Approach 1 (hash map): create a mapping from original node to cloned node. First pass: clone all nodes (store in map). Second pass: set next and random pointers using the map. Time: O(N), Space: O(N). Approach 2 (interleave): insert cloned nodes between original nodes (A -> A_clone -> B -> B_clone). Set clone random pointers: clone.random = original.random.next. Separate the lists. Time: O(N), Space: O(1) extra. Flatten a multilevel doubly linked list: DFS — when a child pointer is encountered, recurse into the child list, then reconnect. Use a stack or recursion. LRU Cache: combine a doubly linked list (for O(1) removal and insertion at head/tail) with a hash map (for O(1) lookup by key). On access: move the node to the head (most recently used). On eviction: remove the tail (least recently used). This is one of the most frequently asked linked list design questions.