Leetcode # 21. Merge Two Sorted Lists

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

Solution

Time Complexity: O(len(list1) + len(list2))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    cur1, cur2 = list1, list2
    root = ListNode()
    cur = root
    while cur1 or cur2:
      if not cur1:
        cur.next = cur2
        return root.next
      elif not cur2:
        cur.next = cur1
        return root.next
      
      if cur1.val <= cur2.val:
        cur.next = cur1
        cur1 = cur1.next
      else:
        cur.next = cur2
        cur2 = cur2.next
      
      cur = cur.next
        
    return root.next

Last Updated on 2023/08/16 by A1go