Amazon Online Assessment (OA) - Merge Two Sorted Lists
Merge two sorted linked lists and return them as a new sorted list. The new list should be made by splicing together the nodes of the two given 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
l1andl2are 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)))
341import 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}
681merge :: [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
14Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.