Merge Two Sorted Lists

Problem Summary

Given the heads of two already sorted Linked List, return the merged sorted Linked List

What is Being Asked?

Solve it with $O (1)$ space complexity

Key Observations

Approach Taken

both list could be of diff lengths
start with dummy node
with two pointers, pick the smallest or equal and append to current
move pointer to next for the list that you picked from
if one list is empty, iterate through each item in remaining list and put all of them in

Main Concepts Used

Time & Space Complexity

Time: $O (n + m)$ → Reason: Iterate through each Linked List once
Space: $O (1)$ → Reason: Just using pointers and not copying the input

Code

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

        dummy = ListNode()
        p1, p2, cur = list1, list2, dummy

        while list1 and list2:
            if list1.val <= list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next

        while list1:
            cur.next = list1
            list1 = list1.next
            cur = cur.next
        while list2:
            cur.next = list2
            list2 = list2.next
            cur = cur.next

        return dummy.next

Optimizations

We do not need to iterate through rest of the items. Its just pointers. We can set the next element to the remaining list.

if list1:
	cur.next = list1
else:
	cur.next = list2

Recursive Solution

class Solution:
    def mergeTwoLists(
        self, list1: Optional[ListNode], list2: Optional[ListNode]
    ) -> Optional[ListNode]:
        if not list1 or not list2:
            return list1 or list2

        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2