Merge Two Sorted Lists

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.

This is a typical linked list question, except that we have to track two linked lists at the same time. Since both lists are sorted, we know that the heads of both are the smallest elements of their respective list. We can then build the resulting sorted list from scratch using this fact:

• Compare the heads of each list.
• Append the smaller one of the two to the final linked list.
• Iterate the appended list one node forward to point to the next node.
• Repeat until there are no more nodes to append.

Since list1 and list2 are not guaranteed to be the same length, there may be a point where one list is empty and the other is not. In this case, since both are sorted, we can simply append on the rest of the nodes to the final list without breaking the order.

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
	head = ListNode()  # dummy node to keep track of the start
	curr = head
	
    # loop invariate: list1.head and list2.head are bigger than or equal to curr
	while list1 is not None and list2 is not None:
		if list1.val < list2.val:
			curr.next = ListNode(list1.val)
			list1 = list1.next
		else:
			curr.next = ListNode(list2.val)
			list2 = list2.next
		
		curr = curr.next

    # add any remaining nodes to the final linked list
    if list1 is None:
        curr.next = list2
    elif list2 is None:
        curr.next = list1
	
	return head.next

Time Complexity

Notice we only iterate until one list is exhausted, at which point we simply append the rest of the other list to our result and return it. Therefore, there are $\min(n_1, n_2)$ iterations in the while loop, and since each iteration is constant time, the loop is in $\mathcal{O}(\min(n_1, n_2))$ time. Since every other operation is constant time, the algorithm is in $\mathcal{O}(\min(n_1, n_2))$ time.

Space Complexity

We only use constant variables to track the current node and head node, and since the space of the result is not counted, we have constant space complexity.