DSA Roadmap/Linked List

Advanced Linked List Manipulation & Design

Group reversal, deep-copying graphs disguised as lists, and the hash-map-plus-doubly-linked-list combo behind LRU/LFU cache design.

!!3/5Theory: 2h 10m7 problems

From technique to design

Everything in Core Linked List Techniques was about correctly manipulating a list you're handed. This subtopic is where linked lists become a design tool: you'll combine them with hash maps to build data structures with O(1) operations, reverse them in structured chunks instead of all at once, and deep-copy a list that's secretly a small directed graph. This cluster — especially LRU/LFU cache design — is one of the most common "design a data structure" questions at the Senior level across every major tech company, precisely because it tests whether you can compose two simple structures (hash map + doubly linked list) into something neither can do alone.

Reversal in groups: extending the single-pass reversal

Reversing an entire list is one operation. Reversing it in fixed-size chunks, leaving a trailing partial chunk untouched, forces you to track multiple "boundary" pointers simultaneously — the group's incoming connection, its outgoing connection, and where the previous group's traversal left off.

Rotate List uses a different two-pointer idea from the core subtopic: the fixed-gap (k-offset) trick. After one pass to record length and tail, reduce k modulo length, advance fast by k steps from head, then walk slow and fast together until fast is on the last node — slow is then the node before the new head. Close the list into a ring (tail.next = head), break at slow, and return slow.next. Same head-start mechanics as Remove Nth Node From End of List, different relinking at the end.

The generic template: to reverse one bounded segment [start, end) (a half-open range, end may be None), you can reuse the exact three-pointer reversal loop from the core subtopic, just bounded by a stopping node instead of running to None:

def reverse_range(start, end): """Reverses nodes from `start` up to (not including) `end`. Returns the new head of this reversed segment (== the old tail).""" prev = end curr = start while curr is not end: next_node = curr.next curr.next = prev prev = curr curr = next_node return prev # this is the node that used to be `start`'s predecessor-in-reverse

The outer algorithm's job is bookkeeping: find each group's boundary, call this helper, and correctly reconnect the reversed segment back into the rest of the list — reconnecting group_prev.next to the new head of the reversed group, and letting the old head of the group (now its tail) point to wherever the next group begins.

Key invariant: before you rewire anything, first locate (and hold a reference to) the node immediately after the group you're about to reverse. If you don't grab that reference before reversing, you cannot find your way back into the rest of the list — this is the single most common way this pattern goes wrong.

Complexity: O(n) time — every node is touched a constant number of times regardless of group size. O(1) space for the iterative version; a recursive formulation (recurse to reverse the next group, then reverse the current one) costs O(n/k) stack depth, where k is the group size.

Deep-copying a list with random pointers

Some interview lists aren't simple chains — each node might carry a second pointer (commonly called random) that can point to any node in the list, or None. Structurally, this is a directed graph disguised as a list, and deep-copying it means every pointer in your copy — both next and random — must point to other copied nodes, never back into the original structure.

The obstacle: when you're copying node A and its random pointer targets node D, node D might not have been created yet. You need a way to say "give me the copy corresponding to this original node, creating it on first request."

def copy_random_list(head): old_to_new = {None: None} # sentinel: mapping None -> None avoids null checks below curr = head while curr: old_to_new[curr] = ListNode(curr.val) curr = curr.next curr = head while curr: copy = old_to_new[curr] copy.next = old_to_new[curr.next] copy.random = old_to_new[curr.random] curr = curr.next return old_to_new[head]

Two clean passes: the first pass guarantees every original node has exactly one corresponding copy before any pointer-wiring happens, and the second pass wires both pointer types using pure O(1) dictionary lookups (including the None sentinel trick, so you never special-case a random pointer that happens to be None).

  • Time: O(n) — two linear passes.
  • Space: O(n) for the hash map. There's a well-known O(1)-extra-space variant that interleaves copies directly into the original list (A -> A' -> B -> B' -> ...), reads random pointers off the interleaved structure, then un-weaves the two lists — it's a nice follow-up if asked, but the hash-map version is the one to reach for first: it's less error-prone and the space trade-off is rarely the point of the question.

Gotcha: using object identity (the node itself) as the hash map key, not curr.val — values can repeat across nodes, but each node is a distinct object and must map to a distinct copy.

LRU and LFU cache design: the flagship pattern of this subtopic

This is where linked lists, doubly-linked in particular, combine with the Hash Maps & Hash Sets topic to solve a problem neither structure can solve alone. It's worth internalizing deeply — it is asked constantly, and it's genuinely instructive about why you reach for a doubly linked list instead of a singly linked one.

The requirement that forces the doubly linked list

An LRU (Least Recently Used) cache needs get and put in O(1), evicting the least-recently-touched entry when it's over capacity. Break down what that requires:

  • O(1) lookup by key → a hash map is the obvious answer.
  • O(1) "move this entry to the most-recently-used end" → you need an ordered structure, and you need to relocate an arbitrary entry (not just the head or tail) in O(1). A singly linked list can't do this: removing a node from a singly linked list in O(1) requires a reference to its predecessor, which you don't have unless you store it — which is precisely what a prev pointer is. That's the whole reason the design calls for doubly linked, not singly linked.
  • O(1) "evict whichever entry is least recently used" → keep that entry pinned at one fixed end of the list (say, the node just after a head sentinel), so eviction is always "remove the node right after the sentinel."

The hash map stores key -> node reference (not key -> value!) so that a get can jump straight to the node in the linked list, splice it out, and reinsert it at the most-recently-used end — all O(1), all pointer rewiring, no scanning.

class Node: def __init__(self, key, val): self.key, self.val = key, val self.prev = self.next = None class LRUCache: def __init__(self, capacity): self.cap = capacity self.cache = {} # key -> Node self.left = Node(0, 0) # sentinel: least-recently-used side self.right = Node(0, 0) # sentinel: most-recently-used side self.left.next, self.right.prev = self.right, self.left def _remove(self, node): node.prev.next, node.next.prev = node.next, node.prev def _insert(self, node): prev, nxt = self.right.prev, self.right prev.next = nxt.prev = node node.prev, node.next = prev, nxt def get(self, key): if key not in self.cache: return -1 self._remove(self.cache[key]) self._insert(self.cache[key]) # touching a key = mark as most-recently-used return self.cache[key].val def put(self, key, value): if key in self.cache: self._remove(self.cache[key]) node = Node(key, value) self.cache[key] = node self._insert(node) if len(self.cache) > self.cap: lru = self.left.next self._remove(lru) del self.cache[lru.key]

Why two sentinel nodes (left, right) instead of tracking head/tail as plain node references: exactly the same motivation as the dummy-head trick from the core subtopic — sentinels eliminate null checks when the list is empty or has one element, since _remove and _insert never need to special-case "is this the first/last real node."

Key invariant: the node immediately after left is always the least-recently-used entry, and the node immediately before right is always the most-recently-used. Every get/put on an existing key must remove-then-reinsert to maintain that invariant — forgetting to do this on get (only updating order on put) is the single most common bug reported for this exact problem.

Complexity: O(1) time for both get and put (amortized, no hidden loops). O(capacity) space for the hash map and the list nodes.

LFU: same shape, one more axis of ordering

LFU (Least Frequently Used) eviction is strictly harder: you evict by lowest access frequency, breaking ties by least-recent access within that frequency. The O(1) construction extends the LRU idea by adding a second hash map from frequency → doubly linked list of nodes at that frequency, plus a tracked min_freq. A get/put on a key removes it from its current frequency's list and reinserts it at the front of the (frequency + 1) list; eviction always pulls from the tail of the min_freq list. This is consistently rated Hard on LeetCode, and for good reason — it's two coordinated instances of the LRU mechanism, one nested inside the other.

LRU vs. LFU: comparison

LRU CacheLFU Cache
Eviction criterionLeast recently accessedLowest access frequency (ties broken by recency)
Core structures1 hash map + 1 doubly linked list2 hash maps + 1 doubly linked list per frequency bucket
get/put timeO(1)O(1) (with the frequency-bucket construction)
SpaceO(capacity)O(capacity)
LeetCode calibrationMediumHard
Real-world analogsBrowser cache, CPU cache lines, Redis default evictionContent/CDN caching where popularity matters more than recency

Intersection of two linked lists

Given two singly linked lists that may merge into a shared tail at some node, find that node (or determine there isn't one) — without extra space and without just comparing values (since values can collide; you need to find the same node, i.e., compare by reference/identity).

The elegant O(1)-space trick: walk both lists with two pointers, and when a pointer reaches the end of its list, redirect it to the head of the other list. If the lists intersect at node X, both pointers will have traveled the same total distance (their own list's unique prefix, plus the other list's unique prefix, plus the shared suffix) by the time they reach X — so they arrive there simultaneously. If the lists don't intersect, both pointers simultaneously become None and the loop terminates correctly.

def get_intersection_node(headA, headB): a, b = headA, headB while a is not b: a = a.next if a else headB b = b.next if b else headA return a # either the intersection node, or None if they never meet

Why this is neither a "two pointers" problem in the classic sense nor a hash-set problem: you could trivially solve it in O(n) time / O(n) space with a hash set of visited nodes from the first list, but the pointer-swap trick gets you to O(1) space by exploiting the fact that "swap to the other list's head at the end" exactly equalizes the two total path lengths — a clever, list-specific mechanism rather than a general two-pointer pattern.

Complexity: O(m + n) time, O(1) space.

Pitfalls and interview gotchas specific to this subtopic

  • Grabbing the "next group" boundary too late when reversing in chunks. Once you start rewiring next pointers inside a group, you cannot recover a reference to what came after it unless you saved that reference before the rewiring began.
  • Comparing node values instead of node identity in the intersection problem — two different nodes can legitimately hold the same value, so a.val == b.val is not a valid stopping condition; you need a is b.
  • Forgetting get() must also update recency in an LRU cache — a very frequently cited real bug in submitted solutions.
  • Storing key -> value instead of key -> node in the LRU hash map — you need direct O(1) access to the linked-list node to splice it out, not just its value.
  • Omitting the key inside each linked-list node. When you evict the tail node from the list, you also need to delete its entry from the hash map — which requires knowing its key. If your Node only stores a value, eviction degrades to an O(n) search.
  • Interleaving-approach cleanup in the deep-copy problem. If you use the O(1)-space interleaved variant instead of the hash-map version, forgetting to fully restore the original list's next pointers while extracting the copy leaves both lists corrupted.
  • Off-by-one in the interweave/rebuild loops for any of these composite algorithms (reorder, k-group reversal, LFU bucket management) — these problems chain 2-3 simpler operations together, so a small boundary bug in step 1 corrupts every subsequent step. Test each stage on a tiny hand-traced example (3-4 nodes) before trusting the composed result.

Where this fits in the roadmap

The hash-map-plus-linked-structure idea you just used for LRU/LFU is the same design instinct you'll lean on again once you reach Heaps & Priority Queues (top-K and two-heap patterns) and, later, graph and design-heavy questions — recognizing "I need O(1) lookup and O(1) reordering, so I need two structures working together" is a generalizable interview skill, not a one-off trick specific to caches.

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.