047.md

21. Merge Two Sorted Lists

Difficulty: 🟢 Easy

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.

Examples:

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.

Solutions

O(n+m) solution in Python3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        root = ListNode()
        temp = root
        
        while list1 and list2:
            if list1.val <= list2.val:
                temp.next = list1
                list1 = list1.next
            else:
                temp.next = list2
                list2 = list2.next
            temp = temp.next
            
        temp.next = list1 if list1 else list2
        return root.next

The given solution uses a iterative approach to merge the two sorted linked lists, list1 and list2, into a single sorted list.

The algorithm works as follows:

1. Create a new linked list with a dummy node as the root to keep track of the merged list.
2. Initialize a temporary pointer, temp, to the root.
3. Compare the values of the current nodes in list1 and list2.
4. Append the smaller value node to the temp.next and move the corresponding pointer (list1 or list2) to the next node.
5. Move the temp pointer to the next node as well.
6. Repeat steps 3-5 until either list1 or list2 becomes None.
7. Append the remaining nodes of the non-empty list (list1 or list2) to the end of the merged list.
8. Return the root.next as the head of the merged linked list.

Analysis of Time and Space Complexity

The time complexity of this algorithm is O(n + m), where n and m are the lengths of list1 and list2, respectively. The algorithm iterates through both lists once to merge them.

The space complexity of the algorithm is O(1) since it only uses a constant amount of extra space to create the merged list and update the pointers.

Summary

The given solution merges two sorted linked lists into a single sorted list by comparing the values of nodes and splicing them together. It has a time complexity of O(n + m) and a space complexity of O(1), making it an efficient solution for the problem at hand.

NB: If you want to get community points please suggest solutions in other languages as merge requests.