21. Merge Two Sorted Lists

EasyLinked ListTwo PointersTimeO(m + n)SpaceO(1)

list1

→

list2

→

1vs1

merged

∅

compare heads 1 and 1compare

Frame 1 / 17

1class Solution:
2    def mergeTwoLists(self, list1, list2):
3        head = current = None
4        while list1 and list2:
5            if list1.val <= list2.val:
6                node = list1
7                list1 = list1.next
8            else:
9                node = list2
10                list2 = list2.next
11            if head is None:
12                head = current = node
13            else:
14                current.next = node
15                current = current.next
16        rest = list1 if list1 else list2
17        if head is None:
18            head = rest
19        else:
20            current.next = rest
21        return head