21. Merge Two Sorted Lists

At a Glance

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

Problem (one-liner)

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

Recognition Cues

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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;
}