[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

solution

If 1 list is completely empty, the answer is just the other linekd list. Also, there might be cases where 2 lists are of different lengths or rest of the nodes are not processed even when they have same length like that below example. In this case, we have to add the rest of the nodes at the end. Here, again rmb to update cur pointer to cur.next. I didnt do this and I got it wrong for

list1 = ListNode(-9, ListNode(3))
list2 = ListNode(5, ListNode(7))

where my ans initially gave -9,3,5 and not printing 7 cuz cur was still pointing to 5 and not moving to the right to 7.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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


list1 = ListNode(-9, ListNode(3))
list2 = ListNode(5, ListNode(7))

solution = Solution()
merged_list = solution.mergeTwoLists(list1, list2)

# To print the merged list
while merged_list:
    print(merged_list.val, end=" ")
    merged_list = merged_list.next