LeetCode #21: Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

To solve this problem in Python 3, we can use a simple iterative approach that compares the values of the two input linked lists and creates a new linked list that merges the nodes in sorted order.

Here are the steps to follow:

1. Initialize a new linked list dummy and a pointer tail to None.
2. Compare the values of the two input linked lists at their respective heads.
3. For the smaller value, append a new node to the end of dummy and update tail to point to the new node.
4. Move the pointer of the smaller value’s linked list to its next node.
5. Repeat steps 2 to 4 until one of the input linked lists becomes empty.
6. Append the remaining nodes of the non-empty linked list to the end of dummy.
7. Return the head of dummy.

Here’s the Python 3 code that implements this approach:

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)
        tail = dummy
        
        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        
        if l1:
            tail.next = l1
        else:
            tail.next = l2
        
        return dummy.next

In this code, we first initialize a new linked list dummy and a pointer tail to None. We then compare the values of the two input linked lists at their respective heads. For the smaller value, we append a new node to the end of dummy and update tail to point to the new node. We move the pointer of the smaller value’s linked list to its next node.

We repeat steps 2 to 4 until one of the input linked lists becomes empty. We then append the remaining nodes of the non-empty linked list to the end of dummy.

Finally, we return the head of dummy.

Time and Space Complexity

The time complexity of this approach is O(m+n), where m and n are the lengths of the two input linked lists, because we need to iterate over each node in both linked lists once. The space complexity is O(1) because we only use a constant amount of extra space to store the pointers dummy and tail.