Amazon Online Assessment (OA) - Merge Two Sorted Lists

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

1use 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}
75

1Node = 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
41

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