21. Merge Two Sorted Lists

Description:

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

'''
[1] linear-merge)

code::
def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    dummy=ListNode(-1,None)

    r1,r2=l1,l2 # reader1 and reader2
    w=dummy     # writer

    while r1!=None and r2!=None:
        if r1.val>r2.val:
            w.next=r2
            r2=r2.next
        elif r1.val==r2.val:
            w.next=r1
            r1=r1.next
            w=w.next
            w.next=r2
            r2=r2.next
        else:
            w.next=r1
            r1=r1.next
        w=w.next

    if r1!=None:
        w.next=r1
    if r2!=None:
        w.next=r2
    return dummy.next
    
-T/C: O(m+n) # m==len(list1), n==len(list2)
-S/C: O(1)
'''
class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy=ListNode(-1,None)
        
        r1,r2=l1,l2 # reader1 and reader2
        w=dummy     # writer
        
        while r1!=None and r2!=None:
            if r1.val>r2.val:
                w.next=r2
                r2=r2.next
            elif r1.val==r2.val:
                w.next=r1
                r1=r1.next
                w=w.next
                w.next=r2
                r2=r2.next
            else:
                w.next=r1
                r1=r1.next
            w=w.next
            
        if r1!=None:
            w.next=r1
        if r2!=None:
            w.next=r2
        return dummy.next