Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Reverse Linked List

Problem (restated)

Given the head of a singly linked list, reverse the list in place by rewiring next pointers and return the new head.

Intuition

Each node should point at the node that used to precede it. Walk the list once, keeping the previous node so you can flip cur.next without losing the rest of the list.

Approaches

Three-pointer iterative

Unverified

Time O(n)Space O(1)

Idea. prev, cur, nxt. Save nxt = cur.next, set cur.next = prev, then advance prev = cur, cur = nxt. When cur is null, prev is the new head.

Walkthrough. 1→2→3 → after one step 1←2 3, then 1←2←3. Return 3.

Trade-offs. The template. O(1) extra space, no stack risk. Draw the three pointers before you code; overwriting next without saving nxt drops the tail.

Solution

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 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;
}

Recursive reverse

Unverified

Time O(n)Space O(n) stack

Idea. Base: empty or single node is already reversed. Recurse on head.next to reverse the suffix; then head.next.next = head and head.next = null so the old head becomes the tail.

Walkthrough. Reverse(1→2→3) waits for Reverse(2→3)=3→2, then stitches 1 onto 2.

Trade-offs. Short, but O(n) stack. Interviews want the iterative version unless they ask for recursion.

Solution

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 {
  if (!head || !head.next) return head;
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

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 {
  if (!head || !head.next) return head;
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

Template connection

Direct application of the Linked List Manipulation reverse-whole shape (prev, cur, nxt triple).

Reflection

prev, cur, nxt. Save the next node first, set cur.next = prev, then advance all three. Return prev.
An empty list and a single node are themselves. Overwriting next without nxt drops the tail.
Recursion builds the same reversed list, with stack depth n.