LESSON 373 OF 508 · LINKED LISTS

Merge Two Sorted Lists in Rust

Practice O(n + m)

You are given the heads of two linked lists, list1 and list2. Each list is sorted in ascending order.

Merge the two lists into one sorted linked list and return its head.

Make the merged list by splicing together the nodes of the two lists: link the existing nodes to each other instead of creating new ones. Either list may be empty, and so may both; the head of an empty list is None.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Explanation: The lists are 1->2->4 and 1->3->4.
Each time, the smaller of the two front nodes comes next; on a tie (1 and 1, then 4 and 4),
the node from list1 goes first:
1->1->2->3->4->4

Example 2:

Input: list1 = [], list2 = [0]
Output: [0]
Explanation: list1 is empty, so the merged list is list2 as it is.

Example 3:

Input: list1 = [-4,10,12], list2 = [-7,0]
Output: [-7,-4,0,10,12]
Explanation: -7, -4 and 0 come first, one comparison each. Then list2 is used up,
so the rest of list1, 10->12, follows as it is, without more comparisons:
-7->-4->0->10->12

Constraints:

The number of nodes in each list is in the range [0, 10⁴].
-10⁵ <= Node.val <= 10⁵
Both list1 and list2 are sorted in ascending order; a value can repeat.

Note:

Your algorithm should run in O(n + m) time and use O(1) extra space, where n and m are the lengths of list1 and list2: it only re-links the nodes that are already there.

Start the merged list with a dummy node, an extra node in front of its first real node, so the first node needs no special case: every node is attached after the merged list's last node in the same way, and the answer is the node after the dummy.

Merge the lists in a loop: a recursive merge goes one call deeper for every node, and 2 × 10⁴ nodes can run out of call stack.

STEP 1 OF 13

Guided

Ctrl + Enter to check