21. Merge Two Sorted Lists

Quick Identifier

Topic: linked-list
Pattern: Merge (sorted streams)
Difficulty: Easy
Companies: Amazon, Google, Meta, Bloomberg, Apple
Frequency: Very High
LeetCode: 21

Quick Sights

Time Complexity: O(n+m) from the optimal approach.
Space Complexity: O(1) from the optimal approach.
Core Mechanism: Given ascending singly linked lists listA and listB, merge them into one ascending list and return its head.

Concept Explanation

Given ascending singly linked lists listA and listB, merge them into one ascending list and return its head.

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

Two sorted inputs → one sorted output
Linked list simulation of merge step from mergesort
Dummy node simplifies edge cases

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — O(n+m) time / O(n+m) space — collect values, sort array, rebuild list.
Better — same complexity class but wasteful.
Optimal — O(n+m) time / O(1) extra — walk both heads; always attach smaller node; append remainder.

Optimal Solution

Go

type ListNode struct {
	Val  int
	Next *ListNode
}

func mergeTwoLists(listA *ListNode, listB *ListNode) *ListNode {
	dummy := &ListNode{}
	tail := dummy
	for listA != nil && listB != nil {
		if listA.Val <= listB.Val {
			tail.Next = listA
			listA = listA.Next
		} else {
			tail.Next = listB
			listB = listB.Next
		}
		tail = tail.Next
	}
	if listA != nil {
		tail.Next = listA
	} else {
		tail.Next = listB
	}
	return dummy.Next
}

JavaScript

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

function mergeTwoLists(listA, listB) {
	const dummy = new ListNode();
	let tail = dummy;
	while (listA !== null && listB !== null) {
		if (listA.val <= listB.val) {
			tail.next = listA;
			listA = listA.next;
		} else {
			tail.next = listB;
			listB = listB.next;
		}
		tail = tail.next;
	}
	tail.next = listA !== null ? listA : listB;
	return dummy.next;
}