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

Middle of the Linked List

Problem (restated)

Given the head of a singly linked list, return the middle node. If two middles, return the second.

Intuition

Slow moves one step, fast two; when fast finishes, slow is at the middle.

Approaches

Fast & slow pointers

Unverified

Time O(n)Space O(1)

Idea. Advance until fast is null or fast.next is null; return slow.

Walkthrough. 1→2→3→4→5 → slow ends on 3; even length ends on second middle.

Trade-offs. Counting length first is two passes; this is one pass O(1) space.

Solution

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}
export function middleNode(head: ListNode | null): ListNode | null {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  return slow;
}

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}
export function middleNode(head: ListNode | null): ListNode | null {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  return slow;
}

Template connection

Fast & slow pointers: when fast finishes, slow is at the middle.

Reflection

For an even length, where do slow and fast start so you land on the second middle?
You stop when fast has no next.next. Why does the order of fast && fast.next matter?
Counting the length and walking n // 2 is also correct. What does the single pass buy?