Amazon Online Assessment (OA) - Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the given two lists.
Examples:
Example1:
Input: l1 = [1,2,4]
, l2 = [1,3,4]
Output: [1, 1, 2, 3, 4, 4]
Example 2:
Input: l1 = []
, l2 = []
Output: []
Example 3:
Input: l1 = []
, l2 = [0]
Output: [0]
Constraints:
The number of nodes in both lists is in the range [0, 50]
.
-100 <= Node.val <= 100
- Both
l1
andl2
are sorted in non-decreasing order.
Try it yourself
Solution
1class Node:
2 def __init__(self, val, next=None):
3 self.val = val
4 self.next = next
5
6def merge(l1: Node, l2: Node) -> Node:
7 cur = dummy = Node(0)
8 while l1 and l2:
9 if l1.val < l2.val:
10 cur.next, l1 = l1, l1.next
11 else:
12 cur.next, l2 = l2, l2.next
13 cur = cur.next
14
15 cur.next = l1 or l2
16 return dummy.next
17
18def build_list(nodes, f):
19 val = next(nodes, None)
20 if val is None: return None
21 nxt = build_list(nodes, f)
22 return Node(f(val), nxt)
23
24def format_list(node):
25 if node is None: return
26 yield str(node.val)
27 yield from format_list(node.next)
28
29if __name__ == '__main__':
30 l1 = build_list(iter(input().split()), int)
31 l2 = build_list(iter(input().split()), int)
32 res = merge(l1, l2)
33 print(' '.join(format_list(res)))
34