Merge Two Sorted Lists

Problem in Plain English

You are given the heads of two linked lists that are each sorted in non-decreasing order. Splice their nodes together into one sorted list and return its head.

Problem Statement

You are given the heads of two singly linked lists, list1 and list2, each sorted in non-decreasing order.

Merge the two lists by splicing their existing nodes into one sorted list, then return the head of the merged list.

Assume the two inputs are acyclic and do not share nodes. Reuse every input node exactly once; changing their next links is allowed, but replacing them with copies is not. Equal values may appear in either order; the snippets consistently take list1 first on ties.

Constraints

The number of nodes in each list is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.
The input lists are acyclic and have disjoint node identities; the merge may mutate their next links.

Examples

Example 1

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

Take 1 from list1, 1 from list2, 2 from list1, 3 from list2, and the two 4s. All six original nodes remain, including both occurrences of each repeated value, in non-decreasing order.

Example 2

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

Neither input owns any nodes, so there is nothing to splice and the returned head is null.

Example 3

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

There is no competing head. Return the existing node with value 0 as the whole result, preserving its identity.

Example 4

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

Negative values compare numerically, and equal values are not deduplicated. Both -3 nodes and all three 2 nodes are retained; exhausting list1 still leaves two nodes from list2 to attach.

Intuition

Each sorted list exposes its smallest remaining value at its head, so the smallest remaining value overall must be one of those two heads. In Example 1, choose the first 1, then the other 1, then 2 and 3, and finally both 4s. Keep an output tail to attach each chosen existing node; a temporary dummy node supplies a predecessor even before the first real node is chosen. Node identity matters: a newly allocated node with the same value is still a different node.

Approaches

Collect Nodes and Sort

Solution Details

Reveal Collect Nodes and Sort: intuition, complexity, and code

Intuition

Collect references to all existing nodes, sort those references by node value, and relink them in sorted order. This baseline treats the two inputs as an unordered collection instead of using their sorted heads. Collecting values and rebuilding would produce the right numbers but violate the requirement to splice the original nodes; keeping references preserves ownership.

Step-by-Step Logic

Traverse each input without changing its links and store node references: Example 1 gives [A1(1), A2(2), A3(4), B1(1), B2(3), B3(4)], with A and B identifying the input lists.
Sort the references by their numeric values; Example 1 becomes [A1, B1, A2, B2, A3, B3]. Stable ties keep A1 before B1 and A3 before B3.
Relink each sorted node to its successor: start with A1.next = B1, then B1.next = A2, and continue through A3.next = B3.
Set the final node's next link to null to terminate the chain; return the first sorted reference, or null when the collection is empty. Example 1 returns [1,1,2,3,4,4].

Why It Works

Each acyclic input is traversed once, and disjoint ownership means the reference array contains every original node exactly once. Sorting arranges those references in non-decreasing value order without changing their values. Linking every reference to the next sorted reference visits exactly that sequence; assigning null to the last next link removes any old successor that could create a cycle. Empty input produces null. Stable sorting preserves each input's relative order on ties, and collecting list1 before list2 gives list1 priority for equal values.

Dry Run

Collect Nodes and Sort: variable states at each step
Phase	Current node or link	Reference array	Built prefix after relinking
Collect list1	A1(1)	[A1]	none
Collect list1	A2(2)	[A1,A2]	none
Collect list1	A3(4)	[A1,A2,A3]	none
Collect list2	B1(1)	[A1,A2,A3,B1]	none
Collect list2	B2(3)	[A1,A2,A3,B1,B2]	none
Collect list2	B3(4)	[A1,A2,A3,B1,B2,B3]	none
Stable numeric sort	ascending values	[A1,B1,A2,B2,A3,B3]	none
Relink	A1.next = B1	unchanged	A1 → B1
Relink	B1.next = A2	unchanged	A1 → B1 → A2
Relink	A2.next = B2	unchanged	A1 → B1 → A2 → B2
Relink	B2.next = A3	unchanged	A1 → B1 → A2 → B2 → A3
Relink	A3.next = B3	unchanged	A1 → B1 → A2 → B2 → A3 → B3
Terminate and return	B3.next = null; head = A1	unchanged	[1,1,2,3,4,4]

Complexity Analysis

Time Complexity

O((m + k) \log(m + k))

Space Complexity

O(m + k)

Let m and k be the input lengths. Collection and relinking are linear; general comparison sorting has the displayed worst-case bound (with constant handling for zero or one node). The reference array uses linear auxiliary space, and Java/Python stable sorts may use linear temporary storage; JavaScript sort workspace is engine-dependent, with linear storage in common engines. No replacement data nodes are allocated and the returned chain reuses input nodes.

Code

Solution.java

1import java.util.ArrayList;2import java.util.Comparator;3import java.util.List;4
5class ListNode {6    int val;7    ListNode next;8    ListNode(int val) { this.val = val; }9    ListNode(int val, ListNode next) { this.val = val; this.next = next; }10}11
12class Solution {13    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {14        List<ListNode> nodes = new ArrayList<>();15        for (ListNode curr = list1; curr != null; curr = curr.next) nodes.add(curr);16        for (ListNode curr = list2; curr != null; curr = curr.next) nodes.add(curr);17        // Sort references rather than values so every original node is reused.18        nodes.sort(Comparator.comparingInt(node -> node.val));19        for (int i = 0; i + 1 < nodes.size(); i++) nodes.get(i).next = nodes.get(i + 1);20        if (nodes.isEmpty()) return null;21        // Old links may point elsewhere in the sorted order; explicitly terminate it.22        nodes.get(nodes.size() - 1).next = null;23        return nodes.get(0);24    }25}

Hints

Hint 1

Picture merging two sorted piles by repeatedly taking the smaller visible card.

Hint 2

A dummy node before the merged list removes the special case for choosing its first node.

Hint 3

When one list runs out, the rest of the other list is already sorted, so attach it whole instead of looping node by node.

Edge Cases

Both lists are empty, so the loop never runs and dummy.next is null.
One list is empty, so the answer is the other list attached whole.
All values in one list are smaller, so the other list is spliced on in a single step after the loop.
Repeated values must retain every node; equality never means a duplicate node can be discarded.
Inputs must not share a tail: reusing overlapping nodes without a separate policy can introduce a cycle.

Common Mistakes and Interview Tips

Forgetting to attach the leftover nodes after the loop, which silently drops the tail of the longer list.
Returning dummy or tail instead of dummy.next, which includes the placeholder or only the last node.
Advancing tail without moving it to the appended node, which overwrites the same link every iteration.
Sorting values and allocating replacement nodes satisfies value equality but violates the original-node splicing requirement.
Using JavaScript's default sort compares text representations; compare node values numerically.
Forgetting to terminate the sorted-reference chain can leave an old link pointing backward and create a cycle.

Key Takeaway

Merge sorted linked lists by preserving a chosen-prefix invariant and comparing only exposed heads. A dummy node removes the empty-prefix special case; reference-based rewiring preserves ownership without allocating replacement data nodes.