21. Merge Two Sorted Lists#

Difficulty: Easy

Link to Problem: To see the Merge Two Sorted Lists problem on LeetCode, click here!

You are 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.

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.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(list1, list2):
    # Create a dummy node to simplify the code.
    dummy = ListNode()
    current = dummy

    while list1 and list2:
        if list1.val < list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next

    # Append the remaining elements from either list.
    if list1:
        current.next = list1
    else:
        current.next = list2

    return dummy.next

Explanation:#

  1. We define a class ListNode to represent the nodes of a singly-linked list. Each node has a val attribute to store the value of the node and a next attribute to point to the next node in the list.

  2. We define the mergeTwoLists function that takes two linked list heads, list1 and list2, as input.

  3. We create a dummy node at the beginning of the merged list. The dummy node simplifies the code by serving as a placeholder, and its next attribute will point to the actual merged list.

  4. We initialize a current pointer to point to the dummy node initially. This current pointer helps us traverse and build the merged list.

  5. We enter a while loop that continues until either list1 or list2 becomes empty. Inside the loop, we compare the values of the nodes at the current positions of list1 and list2.

  6. If the val of the node in list1 is smaller than the val of the node in list2, we attach the node from list1 to the merged list by updating the next attribute of the current node to point to the node in list1. We then move the list1 pointer to the next node.

  7. If the val of the node in list2 is smaller than or equal to the val of the node in list1, we attach the node from list2 to the merged list in a similar manner. We move the list2 pointer to the next node.

  8. After attaching a node to the merged list, we move the current pointer to the newly added node. This step is essential for keeping track of the end of the merged list.

  9. The loop continues until either list1 or list2 becomes empty.

  10. Once the loop exits, we check if there are any remaining elements in list1 or list2. If list1 is not empty, we attach the remaining elements of list1 to the merged list. If list2 is not empty, we attach the remaining elements of list2.

  11. Finally, we return the next attribute of the dummy node as the head of the merged list, which represents the sorted merged list.

# Helper function to print the linked list
def printLinkedList(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

Let’s explain the helper functions: printLinkedList Function:

  • The printLinkedList function takes the head of a linked list as input and returns a list of values representing the nodes in the linked list.

  • Inside the function, a result list is initialized to store the values of the linked list nodes.

  • The function then iterates through the linked list starting from the head node and appends the val attribute of each node to the result list.

  • As it iterates through the list, it moves to the next node using the next attribute of each node.

  • Finally, the function returns the result list containing the values of the linked list nodes in the order they appear in the linked list.

This function is useful for debugging and displaying the contents of a linked list. It allows you to easily convert a linked list into a regular Python list for visualization and testing purposes.

Test cases#

# Example 1:
# Input: list1 = [1,2,4], list2 = [1,3,4]
list1 = ListNode(1, ListNode(2, ListNode(4)))
list2 = ListNode(1, ListNode(3, ListNode(4)))
merged_list = mergeTwoLists(list1, list2)
printLinkedList(merged_list)

[1, 1, 2, 3, 4, 4]

# Example 2:
# Input: list1 = [], list2 = []
list1 = None
list2 = None
merged_list = mergeTwoLists(list1, list2)
printLinkedList(merged_list)

[]

# Example 3:
# list1 = [], list2 = [0]
list1 = None
list2 = ListNode(0)
merged_list = mergeTwoLists(list1, list2)
printLinkedList(merged_list)

[0]

Let’s analyze the time and space complexity of the mergeTwoLists function.

Time Complexity:

The time complexity of this function is \(O(N + M\)), where \(N\) and \(M\) are the lengths of list1 and list2, respectively. Here’s why:

  1. In the worst case, we need to traverse both list1 and list2 completely. This involves iterating through all the nodes in both lists once.

  2. The while loop runs until either list1 or list2 becomes empty. The number of iterations depends on the total number of nodes in both lists, which is N + M in the worst case.

  3. Inside the loop, we perform constant-time operations for each iteration, such as comparisons and updating pointers.

Therefore, the dominant factor in the time complexity is the combined length of both input lists, resulting in a linear time complexity of \(O(N + M)\).

Space Complexity:

The space complexity of this function is \(O(1)\), which means it uses a constant amount of extra space regardless of the input sizes. Here’s why:

  1. We create a few extra pointers (dummy, current) and temporary variables (val) to manage the merging process. These consume a fixed amount of memory, regardless of the input sizes. The number of these extra variables is independent of the lengths of list1 and list2.

  2. We do not create a new data structure or allocate memory for the merged list. Instead, we rearrange the existing nodes from list1 and list2 to form the merged list. This operation does not consume additional memory proportional to the input sizes.

In summary, the mergeTwoLists function has a time complexity of \(O(N + M)\) and a space complexity of \(O(1)\), making it an efficient solution for merging two sorted linked lists.

Challenging Exercises:#

  1. Merge K Sorted Lists: Extend the problem to merge \(K\) sorted linked lists instead of just two. You need to efficiently merge \(K\) lists into one sorted list.

  2. Merge Lists in a Zigzag Pattern: Merge two sorted lists in a zigzag pattern. For example, given [1, 2, 4] and [1, 3, 5], the merged list should be [1, 1, 2, 3, 4, 5].