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:
21 return None
22 nxt = build_list(nodes, f)
23 return Node(f(val), nxt)
24
25def format_list(node):
26 if node is None:
27 return
28 yield str(node.val)
29 yield from format_list(node.next)
30
31if __name__ == "__main__":
32 l1 = build_list(iter(input().split()), int)
33 l2 = build_list(iter(input().split()), int)
34 res = merge(l1, l2)
35 print(" ".join(format_list(res)))
361import 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}
681use std::error;
2use std::fmt::Display;
3use std::io;
4use std::str::FromStr;
5
6type List<T> = Option<Box<Node<T>>>;
7
8struct Node<T> {
9 val: T,
10 next: List<T>,
11}
12
13fn merge(l1: List<i32>, l2: List<i32>) -> List<i32> {
14 match (l1, l2) {
15 (Some(n1), Some(n2)) => Some(Box::new(if n1.val < n2.val {
16 Node {
17 val: n1.val,
18 next: merge(n1.next, Some(n2)),
19 }
20 } else {
21 Node {
22 val: n2.val,
23 next: merge(Some(n1), n2.next),
24 }
25 })),
26 (l1, l2) => l1.or(l2),
27 }
28}
29
30fn build_list<'a, T, I>(iter: &mut I) -> Result<List<T>, Box<dyn error::Error>>
31where
32 T: FromStr,
33 I: Iterator<Item = &'a str>,
34 <T as FromStr>::Err: 'static + error::Error,
35{
36 let val = match iter.next() {
37 Some(val) => val.parse()?,
38 None => return Ok(None),
39 };
40 let next = build_list(iter)?;
41 Ok(Some(Box::new(Node { val, next })))
42}
43
44fn format_list<T: Display>(node: &List<T>, out: &mut Vec<String>) {
45 if let Some(node) = node {
46 out.push(format!("{}", node.val));
47 format_list(&node.next, out);
48 }
49}
50
51fn print_words<T: Display>(v: &Vec<T>) {
52 let mut iter = v.iter();
53 if let Some(val) = iter.next() {
54 print!("{}", val);
55 for val in iter {
56 print!(" {}", val);
57 }
58 }
59 println!();
60}
61
62fn main() -> Result<(), Box<dyn error::Error>> {
63 let mut line = String::new();
64 io::stdin().read_line(&mut line)?;
65 let l1 = build_list(&mut line.split_whitespace())?;
66 let mut line = String::new();
67 io::stdin().read_line(&mut line)?;
68 let l2 = build_list(&mut line.split_whitespace())?;
69 let res = merge(l1, l2);
70 let mut out = Vec::new();
71 format_list(&res, &mut out);
72 print_words(&out);
73 Ok(())
74}
751Node = Struct.new('Node', :val, :next)
2
3def merge(l1, l2)
4 cur = dummy = Node.new(0, nil)
5 while l1 && l2
6 if l1.val < l2.val
7 cur.next = l1
8 l1 = l1.next
9 else
10 cur.next = l2
11 l2 = l2.next
12 end
13 cur = cur.next
14 end
15 cur.next = l1 || l2
16 dummy.next
17end
18
19def build_list(nodes, &f)
20 begin
21 val = nodes.next
22 rescue StopIteration
23 return nil
24 end
25 nxt = build_list(nodes, &f)
26 Node.new(f.call(val), nxt)
27end
28
29def format_list(node, &b)
30 return if node.nil?
31 b.call(node.val.to_s)
32 format_list(node.next, &b)
33end
34
35if __FILE__ == $0
36 l1 = build_list(gets.split.each) { |v| Integer(v, 10) }
37 l2 = build_list(gets.split.each) { |v| Integer(v, 10) }
38 res = merge(l1, l2)
39 puts(to_enum(:format_list, res).to_a.join(' '))
40end
411merge :: [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