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
}

Watch the pointers move, step by step

List: 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.

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.

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.

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.

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