Merge Two Sorted Lists

Merge two sorted linked lists into one sorted list.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Merge Two Sorted Lists: Compare the two frontier nodes, link the smaller after tail, and advance only its source cursor.

Input and goalMerge two sorted linked lists into one sorted list.

Initialize two sorted chainstail=dummy, first=A1, second=B2, and dummy.next=null.

inputA:1->4->7; B:2->3->8fixedPrefixempty

Recognize it

Two sorted node streams must be merged by relinking existing nodes.

Keep true

The path from dummy through tail is the consumed sorted prefix; first and second begin untouched suffixes. The old link after tail may remain until the next attachment overwrites it.

Reuse it

Emit the smaller frontier and advance only its source; append the remaining sorted suffix in constant time.

Pattern: Two pointers plus a dummy start node.

Simple idea: Attach the smaller current node and move only that list. The dummy node removes the special case for choosing the first result node.

def merge_two_lists(first: ListNode | None, second: ListNode | None) -> ListNode | None:
   dummy = ListNode(0)
   tail = dummy

   while first and second:
      if first.val <= second.val:
         tail.next, first = first, first.next
      else:
         tail.next, second = second, second.next
      tail = tail.next

   tail.next = first or second
   return dummy.next

Cost: $O(m+n)$ time and $O(1)$ extra space.

The platform supplies ListNode with val and next; this snippet assumes that definition.