DSA Roadmap/Linked List

Core Linked List Techniques

The core moves — dummy heads, reversal, fast/slow traversal, fixed-gap (k-offset) pointers, and merging — that underpin nearly every linked list question you'll see.

!!!2/5Theory: 2h5 problems

Why linked lists are a different kind of hard

Arrays punish you with complexity mistakes; linked lists punish you with structural mistakes. There's no compiler error for "I forgot to save a reference before overwriting it" — you just silently drop half your list, or wire in a cycle, and the bug only shows up when you try to traverse the result. At a Senior level, the bar isn't "can you reverse a linked list" (you should be able to do that half-asleep) — it's whether you can reason about pointer state precisely enough to get subtle variants right on the first try, and whether you narrate the invariant you're maintaining as you go.

Every technique below reduces to the same discipline: before you overwrite a next pointer, make sure you've already saved whatever you need to keep going. Draw the list as boxes and arrows on the whiteboard (or in your head) — linked list bugs are visual bugs, and the fastest way to catch one is to trace three or four nodes by hand before you trust your loop condition.

Array vs. Linked List vs. Doubly Linked List

You should be able to justify why a problem calls for a linked list instead of a dynamic array, and why doubly-linked matters later in this topic (LRU cache) and not here.

PropertyArray / Dynamic ArraySingly Linked ListDoubly Linked List
Random access (arr[i])O(1)O(n)O(n)
Insert/delete at known positionO(n) (shifting)O(1) (with a reference to the prior node)O(1) (with a reference to the node itself)
Insert/delete at headO(n)O(1)O(1)
Insert/delete at tailO(1) amortized (array), O(n) (list, no tail pointer)O(n) without tail pointer, O(1) with oneO(1) with a tail pointer
Traverse backwardO(1) (just decrement index)Not possibleO(1)
Extra memory per elementNoneOne pointer (next)Two pointers (prev, next)
Cache localityExcellent (contiguous)Poor (scattered allocations)Poor (scattered allocations)

The practical takeaway interviewers expect: linked lists win when you need O(1) insertion/deletion given a reference to the splice point and don't need random access — which is precisely why they show up inside LRU caches, adjacency lists, and deque implementations, and rarely as a first-choice general-purpose container.

The dummy (sentinel) head — eliminate special cases

The single highest-leverage trick in this topic. Any operation that might modify the head of the list (delete the first node, insert before it, merge lists) has an annoying special case: "if this is the head, update the head pointer instead of some node's next." A dummy node erases that branch entirely by guaranteeing there's always a node before the real head.

def remove_value(head, val): dummy = ListNode(0, next=head) prev, curr = dummy, head while curr: if curr.val == val: prev.next = curr.next # unconditionally safe, even if curr was the original head else: prev = curr curr = curr.next return dummy.next # in case the original head itself was removed

Invariant: prev always points to the last node you've decided to keep. Return dummy.next, never the original head variable, since the true head may have changed.

You'll reuse this exact skeleton for merging, partitioning, deduplication, and removal-by-condition problems — it's not a one-off trick, it's the default way to open almost any linked-list-mutation problem.

Reversal — iterative and recursive

Reversal is the "hello world" of pointer manipulation, but it also the clearest illustration of the core rule: save next before you overwrite it.

Iterative (the version you should default to)

def reverse_list(head): prev = None curr = head while curr: next_node = curr.next # save before we clobber curr.next curr.next = prev # reverse the pointer prev = curr # advance prev curr = next_node # advance curr return prev # prev is the new head once curr runs off the end

Invariant at the top of each loop iteration: everything from prev backward is already correctly reversed and terminated; curr is the first node of the still-unprocessed suffix.

  • Time: O(n) — one pass, constant work per node.
  • Space: O(1) — three pointers, no matter how long the list.

Recursive (know it, but understand the space cost)

def reverse_list_recursive(head): if head is None or head.next is None: return head # 0 or 1 node is trivially reversed new_head = reverse_list_recursive(head.next) head.next.next = head # the node after head now points back to head head.next = None # head becomes the new tail; must terminate it return new_head
  • Time: O(n).
  • Space: O(n) — this is the detail people forget. Each recursive call adds a stack frame that stays alive until the base case returns, so a list of length n produces a recursion depth of n. If an interviewer asks "can you do this without extra space?", the answer is "yes, iteratively" — the recursive version is not O(1) space regardless of how little it looks like it allocates.

Classic gotcha: forgetting head.next = None in the recursive version. The original head is now the tail, and if you don't null out its next (which still points forward to the node that used to follow it), you silently create a cycle the moment the two ends of the list are supposed to be disconnected.

Fast & slow pointers on a linked list

This is the linked-list-specific application of the technique covered in depth in the Fast & Slow Pointers subtopic of Two Pointers — if you haven't internalized that subtopic's general framing, do that first. Here, the mechanism is identical, but linked lists are actually the canonical setting for it, since you can't jump to an arbitrary index the way you can with an array.

Finding the middle

def find_middle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow # for even-length lists, this lands on the *second* middle node

Why it works: fast covers two nodes for every one slow covers, so when fast reaches the end, slow has covered exactly half the distance. The loop condition fast and fast.next is the part everyone gets subtly wrong — get it backward (fast.next and fast.next.next) and you'll land on the wrong node for even-length lists, or crash on certain edge cases. Trace it by hand on a 4-node and a 5-node list before you trust your version.

Cycle detection (Floyd's Tortoise and Hare)

def has_cycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: return True return False

Why it works, intuitively: if there's no cycle, fast simply reaches None first. If there is a cycle, once slow enters it, fast is already looping inside it and gains exactly one node of relative distance on slow every iteration — so it's guaranteed to lap slow and land on the exact same node within one full cycle length. This is O(1) space, versus the O(n)-space brute force of tracking visited nodes in a hash set.

Finding where the cycle starts (not just whether one exists) is a two-phase extension: first detect the meeting point as above, then reset one pointer to head and advance both pointers one step at a time — they meet again exactly at the cycle's entry node. The proof is a short piece of algebra relating the distance from the head to the cycle entry, the distance from the entry to the meeting point, and the cycle length; it's worth internalizing once (see the resources below) rather than re-deriving it live in an interview, but you should be comfortable stating that the two-phase approach works even if you don't re-derive why on the spot.

Fixed-gap two pointers (the k-offset trick)

This is not the same as fast/slow above: both pointers move one step per iteration, but you give one pointer a head start of k nodes so they stay a fixed distance apart. On a linked list you can't jump to index n - k, so this is how you reach "the kth node from the end" or "the node just before the new head after a right rotation" in O(n) time and O(1) space.

Template:

def nth_from_end(head, k): """Returns the node k steps from the tail (1-indexed from the end).""" fast = head for _ in range(k): fast = fast.next # head start: fast is k nodes ahead slow = head while fast and fast.next: # stop when fast is on the last node slow = slow.next fast = fast.next return slow

Invariant: after the head start, slow and fast are always exactly k nodes apart. When fast reaches the last node, slow sits k steps before the tail — i.e. at the (k+1)th node from the end, counting from 1.

Canonical problems:

ProblemWhat the gap findsExtra bookkeeping
Remove Nth Node From End of ListNode before the one to delete (k = n)Dummy head so deleting the first node is not a special case
Rotate ListSplit point before the new head (k' = length % k)Find tail, set tail.next = head to close the ring, then break at the split

For rotation, always reduce k modulo list length first — advancing k steps on a list of length n when k >= n just wraps around. A common full solution shape: one pass to find length and tail, k %= n, advance fast k steps from head, walk both until fast.next is None, then fast.next = head and head = slow.next with slow.next = None.

Why this is not "fast moves twice as fast": the 1:2 speed ratio closes or measures half-list distances (middle, cycles). The fixed-gap trick measures k-from-end distances. Interviewers often follow up "how would you remove the nth node from the end?" right after middle/cycle questions — recognize that as a cue to switch templates.

Merging two sorted lists

The linked-list analog of the merge step in merge sort, and a direct application of the dummy-head trick:

def merge_two_lists(l1, l2): dummy = ListNode() tail = dummy while l1 and l2: if l1.val <= l2.val: tail.next, l1 = l1, l1.next else: tail.next, l2 = l2, l2.next tail = tail.next tail.next = l1 if l1 else l2 # splice in whichever list has leftovers return dummy.next

Note this splices existing nodes rather than allocating new ones — you're relinking next pointers, not copying values. That's O(1) auxiliary space beyond the dummy node, versus O(n) if you built a brand-new list of copied values.

  • Time: O(n + m) for two lists of length n and m — each node is visited exactly once.
  • Space: O(1) iterative, O(n + m) if you write it recursively (same stack-depth argument as reversal).

Complexity summary for this subtopic

TechniqueTimeSpace (iterative)Space (recursive, if applicable)
Dummy-head traversal/removalO(n)O(1)—
ReversalO(n)O(1)O(n) stack
Find middle (fast/slow)O(n)O(1)—
Cycle detection (Floyd's)O(n)O(1)—
Fixed-gap (k-offset)O(n)O(1)—
Merge two sorted listsO(n + m)O(1)O(n + m) stack

Pitfalls and interview gotchas

  • Losing the head. The instant you reassign head = head.next (or similar) without having saved the original reference somewhere, you can no longer return the start of the list. Always keep a dummy or an explicitly named original_head around if head itself needs to move during traversal.
  • Off-by-one in fast/slow initialization. Both starting at head vs. starting fast at head.next changes which "middle" node you land on for even-length lists, and changes whether your loop guard needs fast.next.next or just fast.next. Pick one convention, verify it against a 1-node, 2-node, and 4-node list, and stay consistent.
  • Confusing fixed-gap with fast/slow speed ratio. "Advance fast by k, then walk both one step" solves k-from-end / rotation split problems; "advance fast two steps per slow one" solves middle/cycle problems. Mixing the two templates is the most common way to get the wrong node.
  • Forgetting to null-terminate after reversal. Whether iterative or recursive, if the new tail's next still points somewhere (instead of None), you can accidentally leave a cycle in a list that's supposed to be acyclic — this is especially easy to miss in the recursive version.
  • Null pointer dereferences on empty or single-node lists. Always trace your loop condition against head = None and head = single_node before you consider a solution done; these are the two edge cases interviewers check first.
  • Mutating a list while three pointers are all mid-update. Update pointers in a consistent order (usually: save what you need, then overwrite, then advance) — reordering these steps is the single most common source of "it works on paper but not in code" bugs in this topic.
  • Confusing "reverse in place" with "return a new list." Most interview variants want you to relink existing nodes (O(1) extra space), not allocate copies — say so explicitly, since it affects your stated space complexity.

Where this goes next

Every technique here is a building block: reversal reappears (in a harder, grouped form) and merging reappears (as part of a three-step composite algorithm) in Advanced Linked List Manipulation & Design, the next subtopic — including Rotate List, which applies the fixed-gap trick to find a split point and rewire the tail. The fast/slow pattern you practiced here is also the same mechanical idea tested more abstractly in the Fast & Slow Pointers subtopic of Two Pointers and resurfaces again when you get to cycle-detection-flavored problems on functional graphs later in the roadmap.

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.