Merge Two Sorted Lists

The problem. You are given the heads of two sorted linked lists, list1 and list2. Merge them into one sorted list by splicing their nodes together, and return its head.

list1 is 1 -> 2 -> 4 and list2 is 1 -> 3 -> 4. Merged, they become 1 -> 1 -> 2 -> 3 -> 4 -> 4, with nodes from list1 shown in blue and from list2 in yellow.

Example

Input:  list1 = [1, 2, 4], list2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]

Input:  list1 = [], list2 = [0]
Output: [0]

Free account

Keep reading. It's free.

Sign up to read the rest of this lesson: 5 more sections, 2 drawings, a dry-run simulator and code in JavaScript, Python, Java and C++.

Still to come

1. Brute force: pour everything into an array and sort
2. Optimal: recursion — the smaller head goes first
3. Best solution: splice in a loop with a dummy node
Comparing the three approaches
Edge cases to test

Prev Next

Mark completed

Was this helpful?

StackLast-in, first-out — the structure behind call stacks, undo history, and expression parsing.6 lessons · 13 problems
QueueFirst-in, first-out — the structure behind task scheduling and breadth-first traversal.4 lessons · 5 problems
ArraysContiguous, indexable memory — the foundation almost every other data structure builds on.12 lessons · 16 problems

Merge Two Sorted Lists

Example

Keep reading. It's free.

Keep exploring