algoadvance

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.

Clarifying Questions

1. Is there a chance of either of the lists being empty?
   • Yes, either or both lists can be empty.
2. What should be the format of the final merged list?
   • The final merged linked list should be in sorted order.
3. Can the lists have duplicate values?
   • Yes, the lists can have duplicate values.
4. What is the return type of the function?
   • The function should return the head of the merged linked list.
5. Is there any constraint on the size of the input lists?
   • No, there is no constraint on the size of the input lists.

Strategy

1. Initialization:
   • We will use a dummy node to form the merged linked list. This helps to simplify edge cases by providing a non-null starting point.
   • We will maintain a current pointer that will track the end of the merged list.
2. Merge Process:
   • Traverse both lists list1 and list2 simultaneously:
     • Compare the values at the current nodes of both lists.
     • Attach the smaller value node to the merged list.
     • Move the pointer of the list from which the node was taken.
   • If one of the lists is exhausted, attach the remainder of the other list to the merged list.
3. Return the merged list:
   • The dummy node’s next pointer will point to the head of the merged linked list.

Code

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

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    # Initialize dummy node and current pointer
    dummy = ListNode()
    current = dummy
    
    # Traverse both lists
    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
    
    # Attach the remaining nodes, if any
    if list1:
        current.next = list1
    if list2:
        current.next = list2
    
    # Return the merged list starting from the node next to dummy
    return dummy.next

Time Complexity

• Time Complexity: (O(n + m))
  • Where (n) is the length of list1 and (m) is the length of list2.
  • Each node in both lists is processed exactly once.
• Space Complexity: (O(1))
  • Only a few extra pointers are used; the space usage does not grow with the input size.

This solution is optimal for merging two sorted linked lists and ensures that the merged linked list remains sorted.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?