Merge Two Sorted Lists

1. Overview

In this article, we’re going to learn the different ways to merge two sorted lists.

2. Description

Given the heads of two sorted linked lists list1 and list2, merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

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

Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []

Output: []

Example 3:

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

Output: [0]

Constraints

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

3. Solution - Iterative Approach

• We’ll initialize two nodes: prev and curr. Node prev is the one used to return the final result, and the node curr is the one to help us merge the smaller node from the two lists.
• Then we’ll have a while loop to compare the two nodes: we’ll merge the smaller one to curr.next, and then move the smaller node and curr towards the right until either one of the two lists becomes null.
• When either one becomes null, we’ll assign the other non-null one to curr.next and return prev.next.

• Time complexity: O(M+N).

• Space complexity: O(1).

4. Solution - Recursive Approach

• Two base cases: if list1 == null, we’ll return list2; if list2 == null, we’ll return list1.
• In other cases, (which means neither list1 nor list2 is null), if list1.val is smaller than list2.val, we’ll keep moving list1 toward the right. In other cases, we’ll keep moving list2 toward the right by keep making recursive calls.

• Time complexity: O(M+N).

• Space complexity: O(M+N).

5. Conclusion

In this tutorial, we looked into merging two sorted lists using both iterative and recursive approaches.

Don’t just Leetcode, follow the Coding Patterns instead. Grokking The Coding Interview teaches you techniques and questions patterns to ace the coding interviews.