[Coderust] Merge Two Sorted Linked Lists

 

 

Problem

 

 

 

 

---

 

Solution

 

# Definition for singly-linked list.
# 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]:
        dummy = curr = ListNode(0)
        
        # always insert into curr.next
        while list1 and list2:
            # add list1 nodes until we find one that is larger than or equal to list2 node
            if list1.val < list2.val:
                curr.next = list1
                list1 = list1.next
                
            else:
                curr.next = list2
                list2 = list2.next
            
            curr = curr.next
            
        # when one pointer reaches the end of the list, add the rest of the other list to result
        # curr.next is list1 if not None, list2 if list1 is None
        curr.next = list1 or list2 
        
        return dummy.next

Time Complexity

O(N)

 

 

Space Complexity

O(N)