21 merge two sorted lists

AC and Best Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def (self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
fs = ListNode(0)
fp = fs
while l1 != None and l2 != None:
if l1.val < l2.val:
fp.next = l1
l1 = l1.next
else:
fp.next = l2
l2 = l2.next
fp = fp.next
fp.next = l1 if l1 else l2
return fs.next

Time complexity: O(m+n)
Space complexity: O(1)

have two pointer one pointer to l1 and other point to l2
compare node value to find pointer with smaller value, attach it to new list and that pointer go to next