[Leetcode] 21. Merge Two Sorted Lists

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

initial

So i solved reversing a linked list and came to this. V impt trick is

1) use a separate pointer to traverse through the answer linked list. I couldnt think of this and thought I have to directly place ans.next as the next value but then we dont have any pointer left to traverse the answer linked list at the end of our solution.
2) If you use a separate pointer like 1), you HAVE to set the pointer to .next like cur=cur.next after updating the value because you want the pointer to point to next value and so on.

intiial wrong attempt:

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head1=list1
        head2=list2
        prev=ListNode(0,None)
        while head1.next!=None and head2.next!=None:
            if head1.val>head2.val:
                cur = head2
                prev.next = cur
                head1=head1.next
            else:
                cur = head1
                prev.next=cur
                head2=head2.next
        print(prev.next)
        return prev.next

retry mar 4th 2025

Here I didnt use a dummy node but we HAVE to. This head None value is normally when u wanna set a Node's next attribute. But when u need to assign successive nodes to this head, this head needs to be a node cuz it will have next attributes but None doesnt.

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        first, second = list1, list2
        head = None  # 🚨 PROBLEM: `head` starts as None
        while first or second:
            if first.val < second.val:  # 🚨 PROBLEM: What if `first` is None?
                head, head.next = head.next, first.val  # 🚨 PROBLEM: `head` is None initially
                first = first.next
            elif first.val > second.val:  # 🚨 PROBLEM: What if `second` is None?
                head, head.next = head.next, second.val
                second = second.next
            else:
                head, head.next = head.next.next, first.val  # 🚨 PROBLEM: `head.next.next` doesn't exist
                head.next.next = second.val  # 🚨 PROBLEM: `head.next` might be None
                first = first.next
                second = second.next
        return head.next  # 🚨 PROBLEM: `head` is None, so `head.next` causes an error

solution

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

We first create a dummy node and assign a head pointer to point to this dummy node. We can then move this pointer around.

At the final check when either list1 or list2 is still remaining, we assign the whole head.next to list1 or list2.

complexity

O(n + m), where n and m are the lengths of the input lists. and 1 space cuz nodes are objects and they are still constant space.