Merge Two Sorted Lists🚚

Question

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a 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.

Java Solution

Two different solutions with the same time complexity, the first solution is using the iteration method and the second one is using the recursive method.

Time Complexity O(m+n), where m is the size of the first list and n is the size of the second. In the first solution, we are looping through all the elements in both lists, and in the second solution, we are using recursion to move between all the items in both lists.

Solution 1
Code

Solution 2
Code