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 and l2 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