Merge Two Sorted Lists

 

  1. Clarify the problem:

    • The problem requires merging two sorted linked lists into a single sorted linked list.
    • We need to return the head of the merged list.

  2. Analyze the problem:

    • Input: Two sorted linked lists, each represented by its head node.
    • Output: The head of the merged sorted linked list.
    • Constraints:
      • The input linked lists can have 0 or more nodes.
      • The nodes in each linked list are sorted in ascending order.

  3. Design an algorithm:

    • To solve the problem:
      • Create a dummy node to serve as the head of the merged list.
      • Initialize two pointers, curr and prev, both pointing to the dummy node.
      • Iterate through both linked lists simultaneously until either one of them reaches the end.
      • Compare the values of the nodes at the current positions of the two pointers.
      • Move the pointer with the smaller value to its next node and update the curr pointer accordingly.
      • Continue the iteration until both linked lists have been traversed.
      • Attach the remaining nodes (if any) of the non-empty linked list to the end of the merged list.
      • Return the head of the merged list (i.e., the next node after the dummy node).

  4. Explain your approach:

    • To merge two sorted linked lists, we start by creating a dummy node that will serve as the head of the merged list.
    • We initialize two pointers, curr and prev, both pointing to the dummy node.
    • Then, we iterate through both linked lists simultaneously until either one of them reaches the end.
    • At each iteration, we compare the values of the nodes at the current positions of the two pointers.
    • We move the pointer with the smaller value to its next node and update the curr pointer accordingly.
    • We continue this process until both linked lists have been traversed.
    • Finally, we attach the remaining nodes (if any) of the non-empty linked list to the end of the merged list.
    • We return the head of the merged list (i.e., the next node after the dummy node).

  5. Write clean and readable code:


# 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]:
        # Create a dummy node as the head of the merged list
        dummy = ListNode(0)
        current = dummy

        # Compare the values of the nodes in both lists and append the smaller one
        # to the merged list
        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 nodes of the non-empty list to the merged list
        if list1:
            current.next = list1
        else:
            current.next = list2

        # Return the head of the merged list (excluding the dummy node)
        return dummy.next
  1. Test your code:
    • Test case 1:
      • l1: 1 -> 2 -> 4
      • l2: 1 -> 3 -> 4
      • After merging the two lists, the resulting merged list should be: 1 -> 1 -> 2 -> 3 -> 4 -> 4.
python
# Test case 1
l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)

l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)

merged_list = mergeTwoLists(l1, l2)
while merged_list:
    print(merged_list.val, end=" ")
    merged_list = merged_list.next
# Output: 1 1 2 3 4 4
  • Test case 2:
    • l1: 1 -> 2 -> 4
    • l2: None
    • After merging the two lists, the resulting merged list should be: 1 -> 2 -> 4.
python
# Test case 2
l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)

l2 = None

merged_list = mergeTwoLists(l1, l2)
while merged_list:
    print(merged_list.val, end=" ")
    merged_list = merged_list.next
# Output: 1 2 4

  1. Optimize if necessary:

    • The provided solution already uses a two-pointer approach, which is the most efficient approach for merging two sorted lists.
    • Therefore, there is no further optimization needed.

  2. Handle error cases:

    • The algorithm handles the case where either or both of the input linked lists are empty.
    • If both linked lists are empty, the algorithm returns None.

  3. Discuss complexity analysis:

    • The time complexity of the algorithm is O(n + m), where n and m are the lengths of the two input linked lists.
    • The algorithm performs a single pass through both linked lists, comparing the node values and merging them into a new list.
    • The space complexity is O(1) since the algorithm only uses a constant amount of extra space to store the pointers.
Next Post Previous Post