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
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.Iterator;
4import java.util.List;
5import java.util.Scanner;
6import java.util.function.Function;
7
8class Solution {
9    public static class Node<T> {
10        public T val;
11        public Node<T> next;
12
13        public Node(T val) {
14            this(val, null);
15        }
16
17        public Node(T val, Node<T> next) {
18            this.val = val;
19            this.next = next;
20        }
21    }
22
23    public static Node<Integer> merge(Node<Integer> l1, Node<Integer> l2) {
24        Node<Integer> dummy = new Node<>(0);
25        Node<Integer> cur = dummy;
26        while (l1 != null && l2 != null) {
27            if (l1.val < l2.val) {
28                cur.next = l1;
29                l1 = l1.next;
30            } else {
31                cur.next = l2;
32                l2 = l2.next;
33            }
34            cur = cur.next;
35        }
36        cur.next = l1 != null ? l1 : l2;
37        return dummy.next;
38    }
39
40    public static <T> Node<T> buildList(Iterator<String> iter, Function<String, T> f) {
41        if (!iter.hasNext()) return null;
42        String val = iter.next();
43        Node<T> next = buildList(iter, f);
44        return new Node<T>(f.apply(val), next);
45    }
46
47    public static List<String> splitWords(String s) {
48        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
49    }
50
51    public static <T> void formatList(Node<T> node, List<String> out) {
52        if (node == null) return;
53        out.add(node.val.toString());
54        formatList(node.next, out);
55    }
56
57    public static void main(String[] args) {
58        Scanner scanner = new Scanner(System.in);
59        Node<Integer> l1 = buildList(splitWords(scanner.nextLine()).iterator(), Integer::parseInt);
60        Node<Integer> l2 = buildList(splitWords(scanner.nextLine()).iterator(), Integer::parseInt);
61        scanner.close();
62        Node<Integer> res = merge(l1, l2);
63        ArrayList<String> resArr = new ArrayList<>();
64        formatList(res, resArr);
65        System.out.println(String.join(" ", resArr));
66    }
67}
68
1merge :: [Int] -> [Int] -> [Int]
2merge (x : xs) (y : ys)
3  | x < y     = x : merge xs (y : ys)
4  | otherwise = y : merge (x : xs) ys
5merge xs []   = xs
6merge [] ys   = ys
7
8main :: IO ()
9main = do
10  l1 <- map read . words <$> getLine
11  l2 <- map read . words <$> getLine
12  let res = merge l1 l2
13  putStrLn $ unwords $ map show res
14