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.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How do you reverse a linked list iteratively?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use three pointers: prev (starts null), curr (starts at head), next (temporary). Loop while curr is not null: save next = curr.next (preserve the rest of the list), set curr.next = prev (reverse the pointer), advance prev = curr, advance curr = next. When curr is null, prev is the new head. Time: O(N). Space: O(1). This is the most fundamental linked list operation. Variations: reverse between positions left and right (navigate to position left-1, reverse the sublist, reconnect), reverse in K-groups (reverse each group of K nodes, connect groups, leave remainder if fewer than K). The key to all reversal problems: carefully track what each pointer holds before and after the reversal step. Draw the state on paper for the first 2-3 iterations.”}},{“@type”:”Question”,”name”:”What linked list problems can the fast-slow pointer technique solve?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Fast-slow pointers solve four key problems: (1) Find the middle node: slow moves 1 step, fast moves 2. When fast reaches the end, slow is at the middle. Used as a building block for merge sort on linked lists and palindrome checking. (2) Detect a cycle: slow moves 1, fast moves 2. If they meet, there is a cycle. If fast reaches null, no cycle. (3) Find cycle start: after meeting, reset one pointer to head. Advance both at speed 1. They meet at the cycle entry point. (4) Find Nth from end: advance fast N steps first, then move both at speed 1. When fast hits null, slow is at the Nth-from-end node. All these problems exploit the same principle: different pointer speeds create useful positional relationships. The fast pointer scouts ahead while the slow pointer marks a key position.”}},{“@type”:”Question”,”name”:”What is the dummy node technique and when should you use it?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Create a dummy node and set dummy.next = head. Perform all operations relative to dummy. Return dummy.next as the result. The dummy node eliminates edge cases where the head node changes (deletion of head, insertion before head, operating on an empty list). Without a dummy: you need special-case code for head operations. With a dummy: the head is just another node. Example: remove all nodes with value V. Without dummy: while head and head.val == V: head = head.next (special case). Then iterate. With dummy: dummy.next = head. curr = dummy. While curr.next: if curr.next.val == V then curr.next = curr.next.next else curr = curr.next. Return dummy.next. Use the dummy node for: merge operations, partition lists, remove elements, and any problem where the head might change. It costs one extra node allocation but saves multiple lines of edge-case code and prevents bugs.”}},{“@type”:”Question”,”name”:”How do you implement an LRU cache using a linked list?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”LRU (Least Recently Used) cache requires O(1) get, O(1) put, and O(1) eviction of the least recently used item. Data structures: a doubly linked list (for O(1) removal and insertion at head/tail) and a hash map (for O(1) key lookup). The list maintains access order: most recently used at the head, least recently used at the tail. Get(key): look up in hash map. If found, move the node to the head (most recently used), return value. If not found, return -1. Put(key, value): if key exists, update value and move to head. If key is new: if at capacity, remove the tail node (LRU) and delete from hash map. Create a new node, insert at head, add to hash map. The doubly linked list enables O(1) removal from any position (given a node reference from the hash map) and O(1) insertion at head. This is one of the most commonly asked linked list design problems.”}}]}