21. Merge Two Sorted Lists

This post explores solutions for the problem Merge Two Sorted Lists from LeetCode, with multiple approaches discussed.

Problem Overview

Given two linked lists list1 and list2, both sorted in non-decreasing order. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

My First Solutions

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None:
            return list2
        if list2 is None:
            return list1
        
        # choose minimum value as head
        if (list1.val <= list2.val):
            head = list1
        else:
            head = list2
        
        while list1 is not None and list2 is not None:
            if (list1.val <= list2.val):
                while (list1.next is not None and list1.next.val <= list2.val):
                    list1 = list1.next # loop till the last smaller or eq elem
                buff = list1
                list1 = list1.next
                buff.next = list2 # insert node
                if (head is list2):
                    head = buff
                if (list1 is None):
                    return head
            else:
                while (list2.next is not None and list2.next.val < list1.val):
                    list2 = list2.next # loop till the last smaller elem
                buff = list2
                list2 = list2.next
                buff.next = list1 # insert node
                if (head is list1):
                    head = buff
                if (list2 is None):
                    return head
        return head

Problems with Kangwei’s Solution

Time complexity

In the worst case, each iteration moves one node forward. Since there are m nodes in list1 and n nodes in list2, the worst-case time complexity is O(m + n)

Space Complexity

The space complexity is O(1) because no additional data structures are used to store nodes

Suboptimal Parts

Hard to read
The solution could be simplified by eliminating redundant checks for head inside the loop.
There's no need to recheck the head pointer each time, as the head of the merged list is already determined at the beginning.
The while loops within each branch are more complex than necessary. Instead of iterating manually through each node, we can streamline the process by reassigning pointers.

Revised version:

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

        # Determine the head of the new list
        if list1.val <= list2.val:
            head = list1
            list1 = list1.next
        else:
            head = list2
            list2 = list2.next

        # Pointer to the last processed node
        current = head

        # Iterate through both lists
        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next

        # If one list is not fully traversed, link the rest
        if list1:
            current.next = list1
        else:
            current.next = list2

        return head

Optimal solution (generated by ChatGPT):

A more standard and simpler way to merge two sorted linked lists is by maintaining a dummy node to simplify the process and iterating through both lists with a single loop. Here's a more optimized solution:

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # Initialize a dummy node to simplify edge cases
        dummy = ListNode(-1)
        current = dummy
        
        # Traverse both lists
        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next
        
        # If either list is not empty, append the remaining elements
        current.next = list1 if list1 else list2
        
        # Return the merged list starting from dummy.next
        return dummy.next