Linked lists

What you're giving up, and what you get for it

Doubly linked lists — pay more memory, get backward traversal free

class DoublyListNode {
  constructor(val, prev = null, next = null) {
    this.val = val;
    this.prev = prev;
    this.next = next;
  }
}

// removing a known node is O(1) — no need to walk to find its predecessor
function removeNode(node) {
  if (node.prev) node.prev.next = node.next;
  if (node.next) node.next.prev = node.prev;
}

In a singly linked list, deleting a known node still requires its predecessor (to repoint .next) — and finding the predecessor means walking from the head, O(n). A doubly linked list already has .prev sitting right there, which is exactly why real-world LRU caches (advanced tier) are almost always built on one: O(1) move-to-front and O(1) eviction of a known node.

The node and the walk

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function traverse(head) {
  let node = head;
  while (node !== null) {
    console.log(node.val);
    node = node.next; // the ENTIRE reason lists are O(n) to access by index
  }
}

Reversal — the pattern that trips people up live

function reverseList(head) {
  let prev = null;
  let curr = head;
  while (curr !== null) {
    const next = curr.next;  // save before you overwrite it
    curr.next = prev;        // flip the pointer
    prev = curr;              // advance both
    curr = next;
  }
  return prev; // prev is the new head
}

Dry run: reverseList(1 → 2 → 3 → null)

The list is genuinely broken into two disconnected pieces mid-flip at every step — that's expected, not a bug. It only becomes one connected list again at the very end, once every node's .next has been repointed backward.

Fast/slow pointers — find the middle in one pass

function findMiddle(head) {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;      // moves 1 step
    fast = fast.next.next; // moves 2 steps
  }
  return slow; // when fast hits the end, slow is at the middle
}

This is the same fast/slow idea from the two-pointers chapter, adapted to a structure with no indices — you can't do arr[Math.floor(arr.length/2)] here, so the two-speed walk is how you find the middle without a second pass to count length first.

Cycle detection — Floyd's algorithm

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true; // they lapped each other
  }
  return false; // fast hit null — no cycle
}

If there's a cycle, the fast pointer (moving 2x speed) is guaranteed to eventually land on the same node as the slow pointer — think of two runners on a circular track at different speeds, the faster one always laps the slower one. If there's no cycle, fast simply reaches null first.

Finding WHERE the cycle starts — Floyd's phase two

Detecting a cycle only answers yes/no. The harder follow-up — "return the node where the cycle begins" — has a genuinely elegant second phase: once slow and fast meet, reset one pointer to the head and advance both remaining pointers one step at a time. Where they meet again is the cycle's start.

function detectCycleStart(head) {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      let ptr = head;
      while (ptr !== slow) { // phase two — same speed now
        ptr = ptr.next;
        slow = slow.next;
      }
      return ptr; // the cycle's entry node
    }
  }
  return null; // no cycle
}

Why this works comes down to the math: if the distance from head to the cycle's start is a, and slow/fast meet b steps into the cycle, it can be shown that a equals the remaining distance around the cycle back to the start from the meeting point — which is exactly why walking both pointers at equal speed from those two starting points lands them on the same node. You don't need to re-derive this live; knowing the two-phase shape and being able to state the result is enough.

Floyd on an array — finding the duplicate number

Here is the problem. An array nums holds n + 1 integers, every one of them between 1 and n. By the pigeonhole principle at least one value repeats. Return a repeated value, without modifying the array and with O(1) extra space. Sorting would modify the array, a Set would cost O(n) space, and counting values into a second array costs O(n) as well. The constraint that rules all three out is the hint that something cleverer is going on.

The trick is to see a linked list that was never drawn. Treat index i as a node and nums[i] as its next pointer. Every value is between 1 and n, so every pointer lands on a real index, and no pointer ever leads back to index 0 (zero is never a value). Every node has exactly one outgoing pointer and none of them is null, so a walk that starts at index 0 can never end. With only n + 1 nodes it must eventually revisit one, which means it enters a cycle.

Now ask who points at the node where the cycle begins. One pointer comes from inside the cycle, closing the loop. Another comes from the tail, the path that led in from index 0 — and that tail is never empty, because index 0 itself is not on the cycle (nothing points to it). Two different indices holding the same value is exactly a duplicate. So the entry node of the cycle is a repeated value, and finding it is the two-phase Floyd algorithm you already wrote, with nums[i] standing in for node.next.

function findDuplicate(nums) {
  let slow = 0;
  let fast = 0;
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast); // meet somewhere inside the cycle

  slow = 0; // phase two: same speed, one from the start, one from the meeting point
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }
  return slow; // the cycle's entry is the value that two indices point at
}

Dry run: findDuplicate([1, 3, 4, 2, 2])

The pointers are 0 → 1, 1 → 3, 2 → 4, 3 → 2 and 4 → 2. Walking from index 0 gives 0, 1, 3, 2, 4, 2, 4, …: a tail of 0, 1, 3 leading into the cycle 2 ⇄ 4.

The answer 2 appears at indices 3 and 4, the two pointers that arrive at node 2. Each phase takes at most about as many steps as there are nodes, and the tail plus the cycle never exceed n + 1 nodes, so the time is O(n) and the space is O(1).

There is a different route with the same space cost: binary search on the value, counting how many numbers are at most mid. It runs in O(n log n) time, so the Floyd version is the faster of the two. The practice list includes ex-find-duplicate-number for this one.

Merging two sorted lists — the dummy node in action

function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0);
  let tail = dummy;

  while (l1 !== null && l2 !== null) {
    if (l1.val <= l2.val) {
      tail.next = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      l2 = l2.next;
    }
    tail = tail.next;
  }
  tail.next = l1 !== null ? l1 : l2; // attach whatever's left
  return dummy.next;
}

This is the exact merge() step from merge sort (the sorting chapter), just applied to linked lists instead of arrays — and it's O(1) space here instead of O(n), because nodes are relinked in place rather than copied into a new array.

Merge sort on a list, and merging K sorted lists

Merge sort is the sorting algorithm that fits a linked list, and it is easy to see why. Quicksort and heapsort jump around by index, which a list cannot do. Merge sort only needs to split a sequence and to merge two sorted ones, and both are sequential walks. The merge you already wrote relinks nodes in place, so there is no auxiliary array at all: the only memory the sort needs is its recursion stack.

function sortList(head) {
  if (head === null || head.next === null) return head;

  let slow = head;
  let fast = head.next; // starting fast one step ahead makes slow stop at the END of the first half
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  const second = slow.next;
  slow.next = null; // cut the list in two

  return mergeTwoLists(sortList(head), sortList(second));
}

The one decision that decides whether this works is where slow stops. The findMiddle function from earlier starts both pointers at head and returns the second middle of an even-length list. That is the wrong node here, because we need the last node of the first half so that slow.next = null cuts the list cleanly in two. Starting fast one step ahead, at head.next, shifts the stopping point one node earlier.

Dry run: sortList(4 → 2 → 1 → 3)

Complexity. Every level of the recursion walks and merges each node a constant number of times, and halving the list gives about log₂ n levels, so the time is O(n log n). The extra space is the recursion stack, O(log n), because the merges relink existing nodes and allocate none. A bottom-up version (merge runs of 1, then 2, then 4 …) reaches O(1) extra space, but the recursive one is what to write first.

Merging K sorted lists

Given k sorted lists with N nodes in total, the obvious plan is to merge them into one result, one list at a time. That is quietly expensive: the accumulated result gets longer with every merge and is walked again each time. With k equal lists, merge number i handles about i lists' worth of nodes, so the total is roughly N · (k + 1) / 2, which is O(N·k).

The fix is to merge in pairs, in rounds: lists 0 and 1, lists 2 and 3, and so on, which halves the number of lists while doubling their length. After log₂ k rounds one list is left, and every round handles each node at most once, so the total is O(N log k).

function mergeKLists(lists) {
  if (lists.length === 0) return null;
  let round = lists;
  while (round.length > 1) {
    const next = [];
    for (let i = 0; i < round.length; i += 2) {
      next.push(i + 1 < round.length ? mergeTwoLists(round[i], round[i + 1]) : round[i]);
    }
    round = next; // half as many lists, each twice as long
  }
  return round[0];
}

Counting how many nodes the merge calls handle, for lists of 100 nodes each:

The pairwise column is exactly N · log₂ k (3,200 × 5 = 16,000), and the one-at-a-time column grows with k itself. A min-heap that always holds the current front node of each list gets the same O(N log k) and is the usual alternative; it is written out in the heaps chapter. Empty entries in lists need no special code, because mergeTwoLists already handles a null input, and an empty lists array returns null from the first line.

Nth from the end — the gap technique

Without knowing the length up front, you can't index from the end directly. The fix: advance one pointer n steps first to create a fixed gap, then move both pointers together — when the lead pointer hits the end, the trailing pointer is exactly n from the end.

function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head);
  let fast = dummy, slow = dummy;

  for (let i = 0; i < n; i++) fast = fast.next; // open the gap

  while (fast.next !== null) { // walk both, gap stays fixed
    fast = fast.next;
    slow = slow.next;
  }

  slow.next = slow.next.next; // slow is right before the target
  return dummy.next;
}

The dummy node earns its keep again here — without it, removing the actual head (when n equals the list's length) would need its own special case.

Two lists that meet — intersection, and adding two numbers

Intersection of two lists

Two singly linked lists may merge: from some node onward they are the very same nodes, not copies, and the tail is shared. Return that first shared node, or null if there is none. The nested-loop answer checks every pair and costs O(m·n). Putting one list's nodes into a Set and scanning the other costs O(m) space. The constant-space answer needs one idea: make both pointers walk the same total distance.

Say list A has x nodes of its own followed by c shared ones, and list B has y of its own followed by the same c. Walk a pointer down A and, when it falls off the end, send it to the head of B. Walk another down B and then onto A. The first pointer covers x + c nodes, then y of B's own, and arrives at the shared part after the same number of steps as the second pointer, which covers y + c and then x. The unequal prefixes have been swapped, so the difference in length cancels out and both pointers land on the first shared node together.

function getIntersectionNode(headA, headB) {
  let a = headA;
  let b = headB;
  while (a !== b) {
    a = a === null ? headB : a.next;
    b = b === null ? headA : b.next;
  }
  return a; // the shared node, or null when the lists never meet
}

Dry run: A = 4 → 1 → 8 → 4 → 5 and B = 5 → 6 → 1 → 8 → 4 → 5

The lists share their last three nodes, 8 → 4 → 5. Call A's own nodes a1, a2 (values 4, 1), B's own nodes b1, b2, b3 (values 5, 6, 1), and the shared ones s1, s2, s3.

Look at step 8: b3 and a2 both hold the value 1, but they are different nodes, so the pointers keep walking. That is why the comparison is a !== b on the nodes and never on .val. If the lists share nothing, both pointers fall off the end of their second list on the same step, a === b === null, and the loop exits returning null without a special case. Each pointer walks at most m + n + 1 steps, so the time is O(m + n) and the space is O(1). Both lists must be free of cycles, or the loop never ends.

Adding two numbers stored as lists

Each list holds one number, one digit per node, with the ones digit first: 2 → 4 → 3 is 342. That order is a gift, because the head is exactly the digit that column addition starts with. Walk both lists together, add the two digits and the carry, write sum % 10 into a new node and carry Math.floor(sum / 10) to the next column. A dummy node and a tail pointer build the result front to back.

function addTwoNumbers(l1, l2) {
  const dummy = new ListNode(0);
  let tail = dummy;
  let carry = 0;
  while (l1 !== null || l2 !== null || carry !== 0) {
    const sum = (l1 !== null ? l1.val : 0) + (l2 !== null ? l2.val : 0) + carry;
    tail.next = new ListNode(sum % 10);
    carry = Math.floor(sum / 10);
    tail = tail.next;
    l1 = l1 !== null ? l1.next : null;
    l2 = l2 !== null ? l2.next : null;
  }
  return dummy.next;
}

342 + 465 gives 7 → 0 → 8, which is 807. The loop condition has three parts for a reason: the lists have different lengths, and a final carry still needs its own node. Adding 9 → 9 and 1 gives 0 → 0 → 1, the 1 coming from the carry alone. The time is O(max(m, n)), and the only memory beyond the answer itself is a few variables.

The dummy-node trick — kills a whole class of edge-case bugs

// remove all nodes with a given value
function removeElements(head, val) {
  const dummy = new ListNode(0, head); // fake node before the real head
  let curr = dummy;
  while (curr.next !== null) {
    if (curr.next.val === val) curr.next = curr.next.next;
    else curr = curr.next;
  }
  return dummy.next; // the real (possibly new) head
}

Without the dummy node, deleting the actual head requires special-case code (there's no "previous" node to repoint). With a dummy node in front, the head is never special — it's just dummy.next like any other node's neighbor. Reach for this trick anytime the head itself might need to change.

Reversing part of a list — a sublist, pairs and groups of k

reverseList reverses everything. Two common variants reverse only part of a list, and both are built from the same pointer dance: reverse positions left to right, and reverse every consecutive group of k nodes. Both need a dummy node, because the first node of the list can be the one that moves.

A sublist, by head insertion

One way is to cut the segment out, call reverseList on it and sew the three pieces back together, which means juggling four pointers. A cleaner way is to reverse in place by head insertion. Let before be the node just ahead of position left, and start the node at position left. Repeatedly take the node right after start and move it to the front of the segment, right after before. Each move grows the reversed prefix by one node, and start slowly drifts to the back without ever being touched. After right − left moves the segment is reversed, and start.next already points at the first node after the segment, so nothing needs reconnecting.

function reverseBetween(head, left, right) {
  const dummy = new ListNode(0, head);
  let before = dummy;
  for (let i = 1; i < left; i++) before = before.next; // node just before position left

  const start = before.next; // first node of the segment; it ends up as the segment's tail
  for (let i = 0; i < right - left; i++) {
    const moving = start.next; // the node to pull to the front of the segment
    start.next = moving.next; // unhook it
    moving.next = before.next; // hang it in front of the current segment head
    before.next = moving; // and make it the new segment head
  }
  return dummy.next;
}

Dry run: reverseBetween(1 → 2 → 3 → 4 → 5, left = 2, right = 4)

The time is O(n): up to left steps to find before, then right − left moves of a few assignments each. The space is O(1).

Pairs, which are groups of two

Swapping every two adjacent nodes is the smallest case. For a pair prev → a → b → next the goal is prev → b → a → next. Order matters: first a.next = b.next so that a already points at the rest, then b.next = a, then prev.next = b. Last, prev = a, since a is now the tail of the swapped pair.

function swapPairs(head) {
  const dummy = new ListNode(0, head);
  let prev = dummy;
  while (prev.next !== null && prev.next.next !== null) {
    const a = prev.next;
    const b = a.next;
    a.next = b.next; // a skips over b
    b.next = a; // b points back at a
    prev.next = b; // the previous pair's tail now leads to b
    prev = a; // a is the tail of the swapped pair
  }
  return dummy.next;
}

The loop condition needs both prev.next and prev.next.next to exist, so an odd node left over at the end stays where it is. On 1 → 2 → 3 → 4 → 5: the first pair gives 2 → 1 → 3 → 4 → 5, the second gives 2 → 1 → 4 → 3 → 5, and then only 5 remains, so the loop stops.

Reversing in groups of k

Now generalise: reverse each consecutive block of k nodes, and leave the final block alone if it has fewer than k nodes. The plan for each block has four steps. Walk k nodes from groupPrev to find the block's last node, kth; if the walk falls off the list, stop. Remember groupNext, the node after the block. Reverse the block with the usual loop, but start prev at groupNext instead of null, so the block's old first node, once flipped, points straight at the rest of the list. Finally hang the reversed block off the previous one: groupPrev.next = kth.

function reverseKGroup(head, k) {
  const dummy = new ListNode(0, head);
  let groupPrev = dummy; // the node just before the current group

  while (true) {
    let kth = groupPrev;
    for (let i = 0; i < k && kth !== null; i++) kth = kth.next;
    if (kth === null) break; // fewer than k nodes left: leave them alone

    const groupNext = kth.next; // first node after the group
    let prev = groupNext; // the group's first node must end up pointing here
    let curr = groupPrev.next;
    while (curr !== groupNext) {
      const next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }

    const newTail = groupPrev.next; // the old first node is now the group's tail
    groupPrev.next = kth; // the old kth node is now the group's head
    groupPrev = newTail;
  }
  return dummy.next;
}

Dry run: reverseKGroup(1 → 2 → 3 → 4 → 5 → 6 → 7, k = 3)

Every node is walked once while looking for kth and once while it is reversed, so the time is O(n) and the space is O(1). A recursive version that reverses a block and recurses on the rest is shorter to write but uses O(n / k) stack. The usual bugs are reversing the short final block anyway (check kth before reversing), and forgetting to move groupPrev to the block's old first node, which is now its tail.

Rearranging without allocating — odd-even, partition and rotate

This family reorders the nodes of a list by relinking them: no new nodes, O(1) extra space. Two techniques cover almost all of it. The first is to build two chains and join them, each with its own dummy head. The second is to turn the list into a ring and cut it somewhere else.

Odd-even: group by position

Gather the nodes at positions 1, 3, 5, … first, followed by the nodes at positions 2, 4, 6, …, each group keeping its order. This is about positions, never about the values stored. Keep an odd pointer and an even pointer, and remember evenHead, because the even chain's start is otherwise lost. Each pass lets odd skip over an even node and then lets even skip over the new odd node.

function oddEvenList(head) {
  if (head === null) return null;
  let odd = head;
  let even = head.next;
  const evenHead = even; // remember where the even chain starts
  while (even !== null && even.next !== null) {
    odd.next = even.next; // odd skips over the even node
    odd = odd.next;
    even.next = odd.next; // even skips over the new odd node
    even = even.next;
  }
  odd.next = evenHead; // stitch the chains together
  return head;
}

The loop test is even !== null && even.next !== null: the second half is needed because the body reads even.next, and the first keeps a one-node list (where even starts as null) from crashing. The time is O(n), the space O(1).

Partition around a value

Move every node with a value below x in front of the others, but keep the original relative order within each side. Two dummy heads give you two chains: append each node to the small or the large chain as you pass it, then join them. Because you reuse the original nodes, one line is easy to forget and costly to forget.

function partition(head, x) {
  const smallHead = new ListNode(0);
  const largeHead = new ListNode(0);
  let small = smallHead;
  let large = largeHead;

  for (let node = head; node !== null; node = node.next) {
    if (node.val < x) {
      small.next = node;
      small = node;
    } else {
      large.next = node;
      large = node;
    }
  }
  large.next = null; // the last large node may still point at a small one
  small.next = largeHead.next;
  return smallHead.next;
}

Removing every node with a given value is the same shape with one chain, and it was written earlier in the dummy-node section.

Rotate right by k: close the ring, cut elsewhere

Rotating 1 → 2 → 3 → 4 → 5 right by 2 gives 4 → 5 → 1 → 2 → 3. Picture the list closed into a ring: rotating does not reorder anything, it only chooses a different place to cut. The new tail is the node at index length − k − 1 and the new head is the node after it. So: walk once to find the length and the old tail, reduce k modulo the length, walk to the new tail, cut, and link the old tail to the old head.

function rotateRight(head, k) {
  if (head === null || head.next === null) return head;

  let length = 1;
  let tail = head;
  while (tail.next !== null) {
    tail = tail.next;
    length++;
  }

  k %= length; // rotating by the length changes nothing
  if (k === 0) return head;

  let newTail = head;
  for (let i = 0; i < length - k - 1; i++) newTail = newTail.next;
  const newHead = newTail.next;
  newTail.next = null; // cut the ring here
  tail.next = head; // close the old end back onto the old head
  return newHead;
}

For the example the length is 5 and k = 2, so the new tail is the node at index 2 (the 3), the new head is the 4, and the old tail 5 is linked back to the 1. Two details cost offers. k can exceed the length (rotating a 5-node list by 7 is rotating it by 2), so take k %= length. And when that leaves k === 0 you must return early: otherwise the "new tail" is the old tail, its next is null, and you return null. The time is O(n) with two walks, the space O(1).

Composing the primitives — palindrome and reorder list

Many "hard" list problems are not new ideas. They are two or three of the earlier pieces glued together: find the middle, reverse the second half, then walk both halves together. Palindrome walks them comparing; reorder walks them weaving. Learn the three pieces and these become assembly.

There is one catch, and it is an off-by-one that the earlier findMiddle invites. For a list like 1 → 2 → 2 → 1 that function returns the second middle, the third node. To split a list we want the end of the first half, the second node. Changing the loop test to fast.next !== null && fast.next.next !== null does it: for an even length slow stops on the last node of the first half, and for an odd length it stops on the exact middle, which stays in the first half.

function endOfFirstHalf(head) {
  let slow = head;
  let fast = head;
  while (fast.next !== null && fast.next.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow; // for an even length this is the LAST node of the first half
}

function isPalindrome(head) {
  if (head === null || head.next === null) return true;

  const firstEnd = endOfFirstHalf(head);
  const secondHead = reverseList(firstEnd.next);

  let a = head;
  let b = secondHead;
  let same = true;
  while (same && b !== null) {
    if (a.val !== b.val) same = false;
    a = a.next;
    b = b.next;
  }

  firstEnd.next = reverseList(secondHead); // put the list back the way we found it
  return same;
}

function reorderList(head) {
  if (head === null || head.next === null) return;

  const firstEnd = endOfFirstHalf(head);
  let second = reverseList(firstEnd.next);
  firstEnd.next = null; // cut, so the first half ends cleanly

  let first = head;
  while (second !== null) {
    const firstNext = first.next;
    const secondNext = second.next;
    first.next = second;
    second.next = firstNext;
    first = firstNext;
    second = secondNext;
  }
}

Dry run: isPalindrome(1 → 2 → 3 → 2 → 1)

The loop runs on b because the reversed second half is never longer than the first. The last line puts the list back the way it arrived. Interviewers often ask whether you mutated the input, and a function that quietly leaves a list half-reversed is a bug in anything that calls it afterwards. The cost is three linear passes plus one more to restore: O(n) time and O(1) space, against the O(n) space of copying the values into an array.

Reorder list: L0 → Ln → L1 → Ln-1 → …

Rearrange 1 → 2 → 3 → 4 → 5 into 1 → 5 → 2 → 4 → 3: first node, last node, second node, second-to-last, and so on. The picture is a zipper. Cut the list after endOfFirstHalf, reverse the second half, and interleave the two halves one node at a time.

Copying a list that has random pointers

Each node now has two pointers: next, and random, which may point at any node in the list, or at null. Build a deep copy: a completely new set of nodes, with the same values and with next and random pointing at the corresponding new nodes. No node of the copy may point into the original.

class Node {
  constructor(val, next = null, random = null) {
    this.val = val;
    this.next = next;
    this.random = random;
  }
}

What makes this harder than copying a plain list is a chicken-and-egg problem. When you create the copy of node 3 and want its random to point at the copy of node 7, that copy does not exist yet. The tempting shortcut, new Node(node.random.val), creates a stray node that merely holds an equal value; the copy's shape is wrong, and two original nodes that shared a random target would now point at two different new nodes.

Approach one: a map from original to copy

Split the work in two passes. The first pass creates every copy and records the correspondence in a Map keyed by the original node objects. The second pass wires next and random by looking up the copy of whichever node the original pointed at. By then every copy exists, so there is nothing left to wait for.

function copyRandomList(head) {
  if (head === null) return null;

  const copyOf = new Map(); // original node -> its copy
  for (let node = head; node !== null; node = node.next) {
    copyOf.set(node, new Node(node.val));
  }
  for (let node = head; node !== null; node = node.next) {
    const copy = copyOf.get(node);
    copy.next = node.next === null ? null : copyOf.get(node.next);
    copy.random = node.random === null ? null : copyOf.get(node.random);
  }
  return copyOf.get(head);
}

Approach two: weave the copies into the list

The map only answers one question: "where is the copy of this node?". If each copy sits immediately after its original in the same list, the answer needs no map: the copy of x is x.next. That gives three passes, with O(1) extra space beyond the new nodes themselves:

1. Insert a copy after every original: A → B → C becomes A → A′ → B → B′ → C → C′.
2. Set copy.random = original.random.next, the copy of the original's random target (or null).
3. Unweave: give each original back its own next, and chain the copies together.

function copyRandomListInPlace(head) {
  if (head === null) return null;

  for (let node = head; node !== null; node = node.next.next) {
    node.next = new Node(node.val, node.next); // the copy sits right after its original
  }
  for (let node = head; node !== null; node = node.next.next) {
    node.next.random = node.random === null ? null : node.random.next; // random's copy is random's neighbour
  }

  const copyHead = head.next;
  for (let node = head; node !== null; node = node.next) {
    const copy = node.next;
    node.next = copy.next; // the original skips its copy
    copy.next = copy.next === null ? null : copy.next.next; // the copy skips the next original
  }
  return copyHead;
}

Complexity. Both versions are O(n) time. The map version needs O(n) extra space for the map, the weave version O(1). To check the claim about time, count how often the code reads a next pointer, using a node class whose next is a getter that increments a counter. The counts for lists of increasing size:

Doubling n doubles both counts: linear in each case, with the weave version doing about three times as many pointer reads in exchange for not needing a map. Keep both in your head. The map is easy to write correctly under pressure; the weave is the follow-up for "can you do it in constant space?".

LRU cache — a hash map plus a doubly linked list with sentinels

Design a cache of fixed capacity with two operations, get(key) and put(key, value), both in O(1). When a put would exceed the capacity, evict the least recently used key. A successful get and every put count as a use.

Each requirement kills one simple structure. A hash map finds a key in O(1) but knows nothing about recency. A list ordered by recency knows what to evict but needs O(n) to find a key. The combination works: a Map from key to list node, and a doubly linked list ordered by recency. The map locates a node in O(1); the list moves it to the front, or removes the last one, in O(1).

The list must be doubly linked. To move a node you first unlink it from the middle, which needs its predecessor, and a singly linked list can only find that by walking from the head, the O(n) cost the earlier doubly linked section warned about. With prev stored in the node, unlinking is two assignments.

Sentinel nodes remove the edge cases. Put two fixed dummy nodes in the list, a head and a tail, which are never removed and never hold data. Every real node then has a real node (or a sentinel) on both sides, so unlink and pushFront are the same few lines whether the list has zero, one or a hundred nodes, with no if (node.prev) checks. The most recent node is always head.next and the least recent is always tail.prev.

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.nodes = new Map(); // key -> node
    this.head = { key: null, value: null, prev: null, next: null }; // sentinel: the most recent node sits after it
    this.tail = { key: null, value: null, prev: null, next: null }; // sentinel: the least recent node sits before it
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  unlink(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  pushFront(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    const node = this.nodes.get(key);
    if (node === undefined) return -1;
    this.unlink(node);
    this.pushFront(node); // a read counts as a use
    return node.value;
  }

  put(key, value) {
    if (this.capacity === 0) return;
    const existing = this.nodes.get(key);
    if (existing !== undefined) {
      existing.value = value;
      this.unlink(existing);
      this.pushFront(existing);
      return;
    }
    if (this.nodes.size === this.capacity) {
      const oldest = this.tail.prev; // the least recently used node
      this.unlink(oldest);
      this.nodes.delete(oldest.key); // this is why a node stores its key
    }
    const node = { key, value, prev: null, next: null };
    this.nodes.set(key, node);
    this.pushFront(node);
  }
}

Three invariants keep the structure honest: the map's keys are exactly the keys of the real nodes in the list; the list runs from most recent (after head) to least recent (before tail); and the size never exceeds the capacity. Every operation preserves them.

Dry run: capacity 2

Complexity. Every operation is a lookup in the map plus a fixed number of pointer assignments, so each is O(1) (the map's lookups, inserts and deletes are O(1) on average). The space is O(capacity): at most that many nodes and map entries exist at once.

A JavaScript Map remembers insertion order, so deleting a key and setting it again moves it to the back, and the first key is the oldest. That makes a short LRU possible with a Map alone, and it is exactly the reference used in the next section. In an interview that asks for the data structure, though, the list-plus-map version is the answer being looked for. The design-problems chapter has a practice exercise, ex-lru-cache, for this one.

Checking pointer code against a simple reference

Pointer code fails quietly. It passes the example in the problem and then breaks on a shape nobody thought of: a self-pointing random, an empty list, a repeated key. The best defence is to write a slow, obviously correct reference next to the real solution and compare them on many small random inputs. Two kinds of check are worth knowing.

A structural check: is it really a deep copy?

For the copy-with-random problem, comparing values is not enough, because value-equal nodes that point at the wrong places look identical in a printout. Instead reduce each list to its shape: for each node, its value and the index of its random target. Two lists with equal shapes are wired the same way. Then separately check that the copy shares no node with the original.

function serializeShape(head) {
  const index = new Map(); // node -> its position in the list
  const nodes = [];
  for (let node = head; node !== null; node = node.next) {
    index.set(node, nodes.length);
    nodes.push(node);
  }
  return nodes.map((node) => [node.val, node.random === null ? null : index.get(node.random)]);
}

function isDeepCopy(original, copy) {
  const originals = new Set();
  for (let node = original; node !== null; node = node.next) originals.add(node);
  for (let node = copy; node !== null; node = node.next) {
    if (originals.has(node)) return false; // the copy borrowed one of the original's nodes
  }
  return JSON.stringify(serializeShape(original)) === JSON.stringify(serializeShape(copy));
}

Both helpers run in O(n) time with a Map or Set, so they can be applied to every random list you generate. Serialize the original before the copy and again after: if the two serializations differ, the copy damaged its input, which is exactly the bug the weave version risks.

A behavioural check: the list against a Map

For the LRU cache the reference is the Map-only version, where the order of the keys is the recency order. Replay the same random sequence of operations on both, and after every step compare the return value and the full recency order, read by walking the real list from head.next to tail.

class ReferenceLRU {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // insertion order = recency order, oldest first
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.capacity === 0) return;
    this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) this.map.delete(this.map.keys().next().value);
  }
}

function checkAgainstReference(capacity, steps) {
  const cache = new LRUCache(capacity);
  const reference = new ReferenceLRU(capacity);
  for (const [op, key, value] of steps) {
    if (op === "put") {
      cache.put(key, value);
      reference.put(key, value);
    } else if (cache.get(key) !== reference.get(key)) {
      return false;
    }
    const order = [];
    for (let node = cache.head.next; node !== cache.tail; node = node.next) order.push(node.key);
    if (order.join() !== [...reference.map.keys()].reverse().join()) return false;
  }
  return true;
}

Feed it sequences such as the following, with a small key range so that hits, misses, updates and evictions all occur:

function randomSteps(count) {
  const steps = [];
  for (let i = 0; i < count; i++) {
    const key = Math.floor(Math.random() * 6);
    steps.push(Math.random() < 0.5 ? ["put", key, i] : ["get", key]);
  }
  return steps;
}

A bug in an unlink or in an eviction shows up within a few steps as a mismatch in order, long before it could show up as a wrong answer. A runaway pointer bug in a test is a hung tab, so when you print a list under test, stop after a limit, for example for (let n = head, i = 0; n !== null && i < 100; n = n.next, i++). Whatever the structure, the habit is the same: a slow reference, many tiny random inputs, and a comparison after every operation instead of once at the end.

The pointer-surgery checklist

Almost every list bug in an interview comes from one of the lines below. Run them as a checklist over any list code before you say it is done.

Recognizing it in an unseen problem

• The prompt gives you a ListNode / "linked list" input directly
• "Reverse," "merge two sorted lists," "detect a cycle," "find the middle," "nth from the end"
• You need O(1) insert/delete and don't need random access by index
• Fast/slow pointers solve it if the ask involves "middle," "cycle," or "nth from the end"
• Need O(1) removal of an arbitrary known node, or backward traversal — reach for doubly linked
• A dummy node removes a special case anytime the head itself might change

Recognising the harder list problems

The basic signals above get you to "this is a list problem". These phrases tell you which of the longer techniques it is.