Linked Lists

Structure

Unlike arrays, linked list nodes are scattered in memory. Each node holds a value and a pointer to the next node.

class ListNode {
  val:  number
  next: ListNode | null
  constructor(val: number, next: ListNode | null = null) {
    this.val  = val
    this.next = next
  }
}
// 1 → 2 → 3 → null
const head = new ListNode(1, new ListNode(2, new ListNode(3)))

vs Arrays:

The trade-off: linked lists excel at insertions/deletions when you already have a reference to the adjacent node. They’re slower for random access.

Traversal

function printList(head: ListNode | null): void {
  let cur = head
  while (cur !== null) {
    console.log(cur.val)
    cur = cur.next
  }
}

The pattern: let cur = head → loop while cur !== null → advance with cur = cur.next.

The dummy head trick

Many operations (insert at head, merge lists, remove nth node) have annoying special cases at the head. A dummy node before the real head eliminates them.

function removeElements(head: ListNode | null, val: number): ListNode | null {
  const dummy = new ListNode(0, head)
  let cur = dummy
  while (cur.next !== null) {
    if (cur.next.val === val) cur.next = cur.next.next  // skip it
    else                      cur = cur.next
  }
  return dummy.next  // the real head (may have changed)
}

Without the dummy, you’d need a special case to handle removing the head itself. With it, the head is treated like any other node.

Reversal

A classic. Three pointers: prev, curr, next.

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null
  let curr = head
  while (curr !== null) {
    const next = curr.next  // save next before we overwrite it
    curr.next  = prev       // reverse the pointer
    prev       = curr       // advance prev
    curr       = next       // advance curr
  }
  return prev  // prev is the new head
}

Walk through with 1 → 2 → 3 → null:

• After iteration 1: null ← 1, curr = 2
• After iteration 2: null ← 1 ← 2, curr = 3
• After iteration 3: null ← 1 ← 2 ← 3, curr = null → return 3

Find middle: slow/fast pointers

Move slow one step, fast two steps. When fast reaches the end, slow is at the middle.

function findMiddle(head: ListNode): ListNode {
  let slow = head, fast = head
  while (fast.next !== null && fast.next.next !== null) {
    slow = slow.next!
    fast = fast.next.next
  }
  return slow  // for even length, returns the first middle
}

This is useful for “split list in half” problems like sorting or palindrome checking.

Cycle detection: Floyd’s algorithm

Two pointers at different speeds will eventually meet inside a cycle, but never on a linear list.

function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head
  while (fast !== null && fast.next !== null) {
    slow = slow!.next
    fast = fast.next.next
    if (slow === fast) return true  // met inside the cycle
  }
  return false
}

Why they meet: Fast gains one step on slow per iteration. Eventually the gap closes to zero inside the loop. On a linear list, fast hits null before they meet.

Finding cycle start: After detection, reset one pointer to head and advance both one step at a time. They meet at the cycle start. (The math works out because the distance from head to cycle start equals the distance from the meeting point to cycle start.)

function detectCycleStart(head: ListNode | null): ListNode | null {
  let slow = head, fast = head
  while (fast !== null && fast.next !== null) {
    slow = slow!.next
    fast = fast.next.next
    if (slow === fast) {
      slow = head          // reset to head
      while (slow !== fast) {
        slow = slow!.next
        fast = fast!.next  // both move one step now
      }
      return slow  // cycle start
    }
  }
  return null
}

Common patterns

Complexity summary