21. Merge 2 Sorted Lists

Problem Statement in English

You’re 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.

Approach

We need to maintain 2 pointers, one for each list.

We will compare the values of the nodes pointed by these pointers and attach the smaller node to the merged list.

Then we move the pointer of the list from which we took the node to the next node.

We will continue this process until we reach the end of one of the lists. After that, we will attach the remaining nodes of the other list to the merged list.

Also, at the beginning to make it easier to handle edge cases, we can create a dummy node that will serve as the starting point of the merged list.

Finally, we will return the next node of the dummy node, which will be the head of the merged list.

And we’re done!

Solution in Python

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

Complexity

• Time: $O(m + n)$
  where $m$ and $n$ are the lengths of the two linked lists.
  

• Space: $O(1)$
  Since we are not using any extra space that grows with the input size, the space complexity is constant.

And we are done.