#21 Merge Two Sorted Lists

frequently reported atBloomberg Amazon Microsoft Google Apple Meta

the problem

In plain words

Merge two sorted linked lists into one sorted list by splicing their nodes together. Return the head of the merged list.

in list1 = [1,2,4], list2 = [1,3,4]

out [1,1,2,3,4,4]

in list1 = [], list2 = []

out []

in list1 = [], list2 = [0]

out [0]

0 ≤ nodes in each list ≤ 50
-100 ≤ Node.val ≤ 100
Both lists are sorted in non-decreasing order

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternMerge sort & merging sorted runs In-place linked-list rewiring

The smallest remaining node is always one of the two current heads. Take it, re-link it after tail, repeat. A dummy head avoids special-casing the first pick.

solutions

From brute force to optimal

Dump all values into a list, sort, build new nodes.

Copy values from both lists.
Sort.
Build a new list.

timeO((n+m) log(n+m))

Sorting ignores that the inputs were already sorted.

spaceO(n+m)

A value list plus brand-new nodes.

javajava.util.*

1class Solution {2    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {3        List<Integer> values = new ArrayList<>();4        for (ListNode p = list1; p != null; p = p.next) values.add(p.val);5        for (ListNode p = list2; p != null; p = p.next) values.add(p.val);6        Collections.sort(values);7        ListNode dummy = new ListNode();8        ListNode tail = dummy;9        for (int v : values) {10            tail.next = new ListNode(v);11            tail = tail.next;12        }13        return dummy.next;14    }15}

The smaller head wins; its next is the merge of everything else.

If one list is empty, return the other.
Smaller head.next = merge(rest).
Return the smaller head.

timeO(n+m)

One call per node.

spaceO(n+m)

Recursion depth equals the total length.

javajava.util.*

1class Solution {2    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {3        if (list1 == null) return list2;4        if (list2 == null) return list1;5        if (list1.val <= list2.val) {6            list1.next = mergeTwoLists(list1.next, list2); // smaller head wins, merge the rest7            return list1;8        }9        list2.next = mergeTwoLists(list1, list2.next);10        return list2;11    }12}

Walk both lists; attach the smaller node to tail; attach the leftover list at the end.

dummy, tail = dummy.
While both non-empty: tail.next = smaller node; advance that list; tail = tail.next.
tail.next = whichever list remains.
Return dummy.next.

timeO(n+m)

Each loop step places one node.

spaceO(1)

Re-links existing nodes; only dummy is new.

javajava.util.*

1class Solution {2    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {3        ListNode dummy = new ListNode();4        ListNode tail = dummy;5        while (list1 != null && list2 != null) {6            if (list1.val <= list2.val) {7                tail.next = list1;8                list1 = list1.next;9            } else {10                tail.next = list2;11                list2 = list2.next;12            }13            tail = tail.next;14        }15        tail.next = (list1 != null) ? list1 : list2;16        return dummy.next;17    }18}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {3        ListNode dummy = new ListNode();4        ListNode tail = dummy;5        while (list1 != null && list2 != null) {6            if (list1.val <= list2.val) {7                tail.next = list1;8                list1 = list1.next;9            } else {10                tail.next = list2;11                list2 = list2.next;12            }13            tail = tail.next;14        }15        tail.next = (list1 != null) ? list1 : list2;16        return dummy.next;17    }18}

in the room

How to say it in the interview

talk track

Mention the dummy node up front and why: the head of the result isn't known yet.
Point out the final tail.next = list1 != null ? list1 : list2 — the leftover is already sorted, so no loop is needed.
Use <= so equal values keep their original order (stable).
If asked for recursion: "the smaller head is first; the rest is a smaller merge" — six lines, but O(n + m) stack.

traps

Forgetting to attach the leftover list after the loop — the tail of the longer list is lost.
Using < instead of <= is still correct, but <= keeps equal values stable (list1 first).

what they ask next

Follow-ups

Merge k Sorted Lists (LC 23)?

Min-heap of the k current heads → O(N log k). Or merge pairs in rounds (divide and conquer), also O(N log k).

Sort List (LC 148) in O(n log n)?

Merge sort: split with slow/fast, sort each half recursively, merge with this exact routine — it is merge sort's merge step.

before you submit

Edge cases to test

One or both lists empty.
Equal values in both lists — take list1's first to stay stable.
One list entirely smaller than the other — the loop ends early and the rest is attached in one step.

practise next