Linked Lists

Linked lists are pointer choreography problems. Most mistakes are not about big-O, they are about losing node references or breaking links in the wrong order.

If you can reason in invariants and pointer ownership, linked lists become deterministic and easy.

Data Model and Variants

Singly linked list

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)))

Doubly linked list

Each node has prev and next. Faster local deletions (if you already have node pointer), but higher memory overhead and more pointer consistency rules.

Linked List vs Array (Practical Trade-Off)

CTO reality:

• in most product code, arrays win due to locality and simpler APIs
• linked lists still dominate interview pointer problems and niche systems structures (LRU internals with doubly linked lists + hashmap)

Pointer Invariant Discipline (Most Important Section)

When mutating a list node, never overwrite the only path to the rest of the list.

Bad pattern:

curr.next = prev
curr = curr.next // now curr points backward, forward chain lost

Safe pattern:

1. save next
2. rewrite link
3. advance pointers

const next = curr.next
curr.next = prev
prev = curr
curr = next

If you remember only one linked-list rule, remember this ordering.

Traversal Basics

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

Always check for null before dereferencing curr.next.

Dummy Node Pattern (Eliminate Head Edge Cases)

Head modifications are where bugs cluster. Dummy node normalizes them.

function removeElements(head: ListNode | null, val: number): ListNode | null {
  const dummy = new ListNode(0, 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
}

Without dummy, deleting original head requires separate branches.

Use dummy for:

• remove nodes
• merge lists
• partitioning
• insertion at possibly-empty head

Pattern 1: Reverse List (Iterative and Recursive)

Iterative

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null
  let curr = head

  while (curr !== null) {
    const next = curr.next
    curr.next = prev
    prev = curr
    curr = next
  }
  return prev
}

Invariant:

• prev is reversed prefix
• curr is first node of not-yet-processed suffix

Recursive

function reverseListRec(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return head

  const newHead = reverseListRec(head.next)
  head.next.next = head
  head.next = null
  return newHead
}

Recursive version is elegant but uses O(n) call stack.

Pattern 2: Merge Two Sorted Lists

function mergeTwoLists(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode(0)
  let tail = dummy
  let l1 = a
  let l2 = b

  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 ?? l2
  return dummy.next
}

Invariant:

• dummy.next..tail is always sorted merged prefix
• remaining nodes in l1/l2 are untouched

Pattern 3: Remove Nth Node from End

Use two pointers with gap n.

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head)
  let fast: ListNode | null = dummy
  let slow: ListNode | null = dummy

  for (let i = 0; i < n; i++) fast = fast!.next

  while (fast !== null && fast.next !== null) {
    fast = fast.next
    slow = slow!.next
  }

  slow!.next = slow!.next!.next
  return dummy.next
}

Why dummy matters:

• if removing original head, slow still points to predecessor (dummy)

Pattern 4: Find Middle and Split

function middleNode(head: ListNode | null): ListNode | null {
  let slow = head
  let fast = head

  while (fast !== null && fast.next !== null) {
    slow = slow!.next
    fast = fast.next.next
  }
  return slow
}

For split (e.g., merge sort), track predecessor of slow to cut list cleanly.

Pattern 5: Cycle Detection (Floyd)

function hasCycle(head: ListNode | null): boolean {
  let slow = head
  let fast = head

  while (fast !== null && fast.next !== null) {
    slow = slow!.next
    fast = fast.next.next
    if (slow === fast) return true
  }
  return false
}

Finding cycle start

function detectCycleStart(head: ListNode | null): ListNode | null {
  let slow = head
  let fast = head

  while (fast !== null && fast.next !== null) {
    slow = slow!.next
    fast = fast.next.next
    if (slow === fast) {
      slow = head
      while (slow !== fast) {
        slow = slow!.next
        fast = fast!.next
      }
      return slow
    }
  }
  return null
}

Proof intuition:

• after meeting, reset one pointer to head
• both move one step
• algebra on distances to cycle entry forces convergence at entry

Pattern 6: Palindrome Linked List (O(1) Extra Space)

Steps:

1. find middle
2. reverse second half
3. compare halves
4. optional: restore list

function isPalindromeList(head: ListNode | null): boolean {
  if (head === null || head.next === null) return true

  // find middle (slow at mid)
  let slow: ListNode | null = head
  let fast: ListNode | null = head
  while (fast !== null && fast.next !== null) {
    slow = slow!.next
    fast = fast.next.next
  }

  // reverse second half
  let prev: ListNode | null = null
  let curr = slow
  while (curr !== null) {
    const next = curr.next
    curr.next = prev
    prev = curr
    curr = next
  }

  // compare
  let p1: ListNode | null = head
  let p2: ListNode | null = prev
  while (p2 !== null) {
    if (p1!.val !== p2.val) return false
    p1 = p1!.next
    p2 = p2.next
  }
  return true
}

Common miss: forgetting that odd-length lists can ignore exact middle node.

Pattern 7: Reverse Nodes in K-Group (High Signal)

This problem checks whether you can combine multiple pointer primitives.

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  if (k <= 1 || head === null) return head

  const dummy = new ListNode(0, head)
  let groupPrev: ListNode | null = dummy

  while (true) {
    // find kth node from groupPrev
    let kth = groupPrev
    for (let i = 0; i < k && kth !== null; i++) kth = kth.next
    if (kth === null) break

    const groupNext = kth.next

    // reverse group [groupPrev.next ... kth]
    let prev = groupNext
    let curr = groupPrev!.next
    while (curr !== groupNext) {
      const tmp = curr!.next
      curr!.next = prev
      prev = curr
      curr = tmp
    }

    const newGroupHead = kth
    const newGroupTail = groupPrev!.next
    groupPrev!.next = newGroupHead
    groupPrev = newGroupTail
  }
  return dummy.next
}

If you can explain this clearly, your linked-list fundamentals are excellent.

Debugging Checklist for Linked List Bugs

1. Did I lose a reference before saving next?
2. Is termination condition correct (curr !== null, fast && fast.next)?
3. Did I accidentally create a cycle while rewiring?
4. Are head deletions handled (dummy node)?
5. For split operations, did I cut (prev.next = null)?
6. For compare operations, did I align halves correctly on odd length?
7. For k-group, did I reconnect both ends of reversed block?

Most failed submissions are one checklist item away from correct.

Common Interview Pitfalls

• Writing recursive solution without mentioning stack cost
• Using node values to compare identity (val) instead of pointer identity (===) for cycle checks
• Forgetting to move tail after attaching node in merge
• Off-by-one in “nth from end” gap creation
• Null dereference in fast/slow loops

Interview Communication Script

Use this structure:

1. “I use a dummy node to normalize head-edge cases.”
2. “I maintain invariant X on prefix/suffix pointers.”
3. “Each node is visited constant times -> O(n) time, O(1) extra space.”

Linked-list interviews are scored heavily on clarity of pointer invariants.

Problem Ladder

Easy

• Reverse Linked List
• Merge Two Sorted Lists
• Linked List Cycle

Medium

• Remove Nth Node From End
• Reorder List
• Add Two Numbers
• Palindrome Linked List

Hard / high-signal

• Reverse Nodes in K-Group
• Merge K Sorted Lists
• Copy List with Random Pointer

Complexity Summary

Final Takeaway

Linked lists are about reference safety + invariants:

• preserve access before rewiring
• move pointers in a controlled order
• prove what each pointer represents at every step

Do this, and even complex linked-list problems reduce to repeatable pointer mechanics.