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 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:
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)))
36
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

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.

Invest in Yourself

Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.

Go Pro