Linked List Manipulation

How to think about it

Linked list manipulation is pointer rewiring. You rarely allocate new nodes; you reassign next pointers to reorder existing ones. The cardinal rule: before you overwrite a next, save the old value so you do not lose the rest of the list. Draw the pointer diagram for every step, off-by-one here is a silent corruption, not a crash.

A dummy head (sentinel) is the single most useful habit. By pointing dummy.next at the real head, you eliminate the “delete / insert at head” special case: every operation becomes a “previous-node” operation, and the new head is always dummy.next.

Template shapes

Shape	Core move	Example
Reverse whole	prev, cur, nxt triple	LC 206
Reverse range [a, b)	Reverse until cur === b	LC 92, LC 25 (k-group)
Merge two sorted	Dummy + compare heads	LC 21
Partition / group nodes	Two dummy tails (left/right), link at end	LC 328

Complexity baseline

O(n) time, O(1) extra space (a handful of pointers). The whole point: avoid copying the list. If you allocate a new list you are doing it the slow way.

From template to problem

1. Identify the operation: reverse, merge, splice, partition, or a combination.
2. Decide where the new head will be - and protect it with a dummy if it can change.
3. Save next before rewriting; null the final next to avoid cycles.
4. Return dummy.next (or the captured new head), never a stale head reference.

/** Linked list manipulation template: reverse + merge with dummy head. */
export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val; this.next = next;
  }
}

export function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let cur = head;
  while (cur) {
    const nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

export function mergeTwoLists(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode();
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a ?? b;
  return dummy.next;
}

/** Linked list manipulation template: reverse + merge with dummy head. */
export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val; this.next = next;
  }
}

export function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let cur = head;
  while (cur) {
    const nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

export function mergeTwoLists(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode();
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a ?? b;
  return dummy.next;
}