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

Merge Two Sorted Lists

Problem (restated)

Given the heads of two sorted singly linked lists, return the head of a single merged sorted list by relinking the original nodes.

Intuition

Both heads are the smallest remaining of their list; pick the smaller, attach to the tail, advance that list. A dummy head removes the empty-list special case.

Approaches

Dummy head iterative

Unverified

Time O(n+m)Space O(1)

Idea. dummy + tail. While both lists non-null, attach the smaller head to tail.next and advance. Append the non-null remainder.

Walkthrough. 1→2→4 and 1→3→4 → 1→1→2→3→4→4.

Trade-offs. O(1) extra space; no recursion depth risk. The canonical interview answer.

Solution

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

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

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

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

Recursive merge

Unverified

Time O(n+m)Space O(n+m) stack

Idea. Base: one null → return the other. Else pick the smaller head, set its .next to the recursive merge of the rest, return it.

Walkthrough. Same example → identical result; the call stack mirrors the merged length.

Trade-offs. Shortest code, but O(n+m) stack space risks overflow on long lists. Iterative is preferred in interviews for the space win.

Solution

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null,
): ListNode | null {
  if (!list1) return list2;
  if (!list2) return list1;
  if (list1.val <= list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  }
  list2.next = mergeTwoLists(list1, list2.next);
  return list2;
}

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null,
): ListNode | null {
  if (!list1) return list2;
  if (!list2) return list1;
  if (list1.val <= list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  }
  list2.next = mergeTwoLists(list1, list2.next);
  return list2;
}

Template connection

Direct application of the Linked List Manipulation merge-two template (dummy head + tail pointer).

Reflection

The dummy’s next is the head of the merge. Each step attaches the smaller head. When one list ends, the other is attached as one piece.
Without the dummy the first node is a special case. Two empty lists answer null.
On equal values either choice stays sorted. Recursion builds the same merge, with depth n.