Merge Two Sorted Lists

The problem

Merge two sorted linked lists into one sorted linked list by splicing together the nodes.

Because both chains are already ordered, the global minimum is always sitting at one of the two current heads. Splice the smaller node into your merged chain and you never need to examine or reallocate the interior of either list.

Full solution

Dummy sentinel with iterative splice: walk both lists once, always attach the smaller head, then wire the non-empty remainder in one O(1) assignment. Same O(n+m) time as the recursive version but O(1) space instead of a call frame per node.

class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None):
        self.val = val
        self.next = next


def merge_two_lists(list1: "ListNode | None", list2: "ListNode | None") -> "ListNode | None":
    dummy = ListNode()
    tail = dummy
    while list1 and list2:
        if list1.val <= list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next
    # one list is exhausted - the other's remainder is already sorted, splice it whole
    tail.next = list1 if list1 else list2
    return dummy.next

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

function mergeTwoLists(list1, list2) {
  const dummy = new ListNode();
  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;
  }
  // one list is exhausted - the other's remainder is already sorted, splice it whole
  tail.next = list1 ? list1 : list2;
  return dummy.next;
}

The theory behind it

Linked List — the ground this problem stands on. All Linked List problems

What Linked List is

A linked list is a chain of separate cargo cars connected by coupling hooks, scattered anywhere across memory rather than sitting in a tidy contiguous row. Each car, called a node, holds a single piece of data and a pointer directing traffic to the address of the next car in line. Because nodes connect only by directional links, jumping straight to the tenth car is impossible without walking past the first nine.

When to reach for it

Choose a linked list when a problem requires frequent insertions and deletions at known positions without shifting whole blocks of surrounding memory. Problems mentioning pointer splicing, reversing subsequences in place, merging sorted streams, or detecting cycles in linear chains strongly point here. It is ideal when total capacity is unpredictable and memory allocation must happen one individual node at a time.

How the pattern works

Think in terms of pointer rewiring before dereferencing. Keep a dummy head node pointing to the start of the list so modifications to the initial item do not require separate edge logic. Always save references to neighboring nodes into temporary variables before cutting or redirecting forward links. When diagnosing loops or locating middle nodes, advance two references simultaneously at differing velocities so traversal completes without supplementary storage.

What each operation costs

Which roles need this problem

Linked List is a core topic for these 3 roles — if you're targeting one of them, this problem is early in your path, not optional.

Secondary for 5 more roles, including Full-Stack Developer, Android Developer, iOS Developer.