21. Merge Two Sorted Lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Input: l1, l2

if l1 is None or l2 is None
    return not None NodeList between l1 and l2

rst ← None
if l1.val < l2.val
  rst ← l1
  l1 ← l1.next
else
  rst ← l2
  l2 ← l2.next

tmp ← rst
while True
  if l1 is None or l2 is None
    tmp.next ← not None NodeList between l1 and l2
    return rst
  if l1.val < l2.val
    tmp.next ← l1
    l1 ← l1.next
  else
    tmp.next ← l2
    l2 ← l2.next
  tmp ← tmp.next

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

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
      if l1 is None or l2 is None:
        return l2 if l1 is None else l1

      rst = None
      if l1.val < l2.val:
        rst = l1
        l1 = l1.next
      else:
        rst = l2
        l2 = l2.next

      tmp = rst
      while True:
        if l1 is None or l2 is None:
          tmp.next = l2 if l1 is None else l1
          return rst
        if l1.val < l2.val:
          tmp.next = l1
          l1 = l1.next
        else:
          tmp.next = l2
          l2 = l2.next
        tmp = tmp.next