21. Merge Two Sorted Lists

Question

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]

Solution 1: DummyNode + Iterative

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummyNode = ListNode()
        prev = dummyNode
        while list1 is not None and list2 is not None:
            if list1.val <= list2.val:
                prev.next = list1
                list1 = list1.next
            else:
                prev.next = list2
                list2 = list2.next
            prev = prev.next

        ### (Slower) Deal with the rest of list
        prev.next = list2 if not list1 else list1
        
        ### (Faster) Deal with the rest of list
        # while list1 is not None:
        #     prev.next = list1
        #     prev = prev.next
        #     list1 = list1.next
        # while list2 is not None:
        #     prev.next = list2
        #     prev = prev.next
        #     list2 = list2.next

        return dummyNode.next

Time Complexity: O(N)
Space Complexity: O(1)

Solution 2: Recursive

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

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/merge-two-sorted-lists/discuss/1826666/C%2B%2B-oror-Easy-To-Understand-oror-2-Approaches-oror-Recursive-oror-Iterative

Follow-up: 88. Merge Sorted Array、148. Sort List

TODO

Time Complexity: O()
Space Complexity: O()