LC Num 21
First I didn’t understand the problem I think. In the sense that I accepted the inputs as two lists and returned a list - Python list. Then I read it and realized they want the operation in Linked lists.
i took some time to recall how to move along a list and finally figured it out.
The other thing that gave me a minor ankle break was when the test case was two empty lists.
Handled that as well eventually.
Here’s the cumulative code -
1class Solution:
2 def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
3 c = []
4 a =[]
5 b=[]
6
7 i = list1
8 j = list2
9 while i:
10 a.append(i.val)
11 i = i.next
12 while j:
13 b.append(j.val)
14 j = j.next
15 i, j = 0 , 0
16 while i < len(a) and j < len(b):
17 if a[i] < b[j]:
18 c.append(a[i])
19 i = i + 1
20 else:
21 c.append(b[j])
22 j = j+1
23 if j < len(b):
24 c.extend(b[j:])
25 elif i < len(a):
26 c.extend(a[i:])
27 if len(c) > 0:
28 listNode3 = ListNode(c[0],None)
29 head = listNode3
30 for i in c[1:]:
31 temp_node = ListNode(i,None)
32 listNode3.next = temp_node
33 listNode3 = listNode3.next
34 else:
35 head = None
36
37 return head
And boom!
By minorly changing the above code to not create lists out of ListNodes initially, a speedup of 2 seconds can be achieved -
1class Solution:
2 def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
3 c = []
4 a =[]
5 b=[]
6
7 i = list1
8 j = list2
9 while i and j:
10 if i.val < j.val:
11 c.append(i.val)
12 i = i.next
13 else:
14 c.append(j.val)
15 j = j.next
16 if j:
17 while j:
18 c.append(j.val)
19 j = j.next
20
21 elif i:
22 while i :
23 c.append(i.val)
24 i = i.next
25 if len(c) > 0:
26 listNode3 = ListNode(c[0],None)
27 head = listNode3
28 for i in c[1:]:
29 temp_node = ListNode(i,None)
30 listNode3.next = temp_node
31 listNode3 = listNode3.next
32 else:
33 head = None
34
35 return head
