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.

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.

Solution

We will have a temporary dummy node as the start of the result list. We will also have a pointer tail that will always points to the last node in the result list, so appending new nodes is easy. Now we will make two pointers, one will point to list1 and another will point to list2.We traverse the lists till one of them gets exhausted. If the value of the node pointing to either list is smaller than another pointer, add that node to our merged list and increment that pointer. The list with remaining elements is added to the merged linked list.

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy_node = ListNode()
        tail = dummy_node

        while list1 and list2:
            if list1.val < list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next
        
        if list1:
            tail.next = list1
        else:
            tail.next = list2
            
        
      
        return dummy_node.next

Time Complexity: O(N + M), where N and M are the size of list1 and list2 respectively.

Space Complexity: O(1)