Facebook Pixel

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
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5class Solution
6{
7    public class Node<T>
8    {
9        public T val;
10        public Node<T> next;
11
12        public Node(T val)
13        {
14            this.val = val;
15        }
16
17        public Node(T val, Node<T> next)
18        {
19            this.val = val;
20            this.next = next;
21        }
22    }
23
24    public static Node<int> Merge(Node<int> l1, Node<int> l2) {
25        Node<int> dummy = new Node<int>(0);
26        Node<int> cur = dummy;
27        while (l1 != null && l2 != null) {
28            if (l1.val < l2.val) {
29                cur.next = l1;
30                l1 = l1.next;
31            } else {
32                cur.next = l2;
33                l2 = l2.next;
34            }
35            cur = cur.next;
36        }
37        cur.next = l1 != null ? l1 : l2;
38        return dummy.next;
39    }
40
41    public static Node<T> BuildList<T>(List<string> strs, Func<string, T> f)
42    {
43        Node<T> node = null;
44        for (int i = strs.Count - 1; i >= 0; i--)
45        {
46            node = new Node<T>(f(strs[i]), node);
47        }
48        return node;
49    }
50
51    public static List<string> SplitWords(string s)
52    {
53        return string.IsNullOrEmpty(s) ? new List<string>() : s.Trim().Split(' ').ToList();
54    }
55
56    public static List<string> FormatList<T>(Node<T> node)
57    {
58        List<string> l = new List<string>();
59        while (node != null)
60        {
61            l.Add(node.val.ToString());
62            node = node.next;
63        }
64        return l;
65    }
66
67    public static void Main()
68    {
69        Node<int> l1 = BuildList<int>(SplitWords(Console.ReadLine()), int.Parse);
70        Node<int> l2 = BuildList<int>(SplitWords(Console.ReadLine()), int.Parse);
71        Node<int> res = Merge(l1, l2);
72        List<String> resArr = FormatList<int>(res);
73        Console.WriteLine(string.Join(' ', resArr));
74    }
75}
76
1"use strict";
2
3class Node {
4    constructor(val, next = null) {
5        this.val = val;
6        this.next = next;
7    }
8}
9
10function merge(l1, l2) {
11    let dummy = new Node(0);
12    let cur = dummy;
13    while (l1 && l2) {
14        if (l1.val < l2.val) {
15            cur.next = l1;
16            l1 = l1.next;
17        } else {
18            cur.next = l2;
19            l2 = l2.next;
20        }
21        cur = cur.next;
22    }
23    cur.next = l1 != null ? l1 : l2;
24    return dummy.next;
25}
26
27function buildList(nodes, f) {
28    const { value, done } = nodes.next();
29    if (done) return null;
30    const next = buildList(nodes, f);
31    return new Node(f(value), next);
32}
33
34function splitWords(s) {
35    return s === "" ? [] : s.split(" ");
36}
37
38function* formatList(node) {
39    if (node === null) return;
40    yield node.val.toString();
41    yield* formatList(node.next);
42}
43
44function* main() {
45    const l1 = buildList(splitWords(yield)[Symbol.iterator](), parseInt);
46    const l2 = buildList(splitWords(yield)[Symbol.iterator](), parseInt);
47    const res = merge(l1, l2);
48    console.log(Array.from(formatList(res)).join(" "));
49}
50
51class EOFError extends Error {}
52{
53    const gen = main();
54    const next = (line) => gen.next(line).done && process.exit();
55    let buf = "";
56    next();
57    process.stdin.setEncoding("utf8");
58    process.stdin.on("data", (data) => {
59        const lines = (buf + data).split("\n");
60        buf = lines.pop();
61        lines.forEach(next);
62    });
63    process.stdin.on("end", () => {
64        buf && next(buf);
65        gen.throw(new EOFError());
66    });
67}
68
1class Node<T> {
2    val: T;
3    next: Node<T> | null;
4    constructor(val: T, next: Node<T> | null = null) {
5        this.val = val;
6        this.next = next;
7    }
8}
9
10function merge(l1: Node<number> | null, l2: Node<number> | null): Node<number> | null {
11    const dummy = new Node<number>(0);
12    let cur = dummy;
13    while (l1 && l2) {
14        if (l1.val < l2.val) {
15            cur.next = l1;
16            l1 = l1.next;
17        } else {
18            cur.next = l2;
19            l2 = l2.next;
20        }
21        cur = cur.next;
22    }
23    cur.next = l1 != null ? l1 : l2;
24    return dummy.next;
25}
26
27function buildList<T>(nodes: Iterator<string>, f: (val: string) => T): Node<T> | null {
28    const { value, done } = nodes.next();
29    if (done) return null;
30    const next = buildList(nodes, f);
31    return new Node(f(value), next);
32}
33
34function splitWords(s: string): string[] {
35    return s === "" ? [] : s.split(" ");
36}
37
38function* formatList<T>(node: Node<T> | null): Generator<string> {
39    if (node === null) return;
40    yield node.val.toString();
41    yield* formatList(node.next);
42}
43
44function* main() {
45    const l1 = buildList(splitWords(yield)[Symbol.iterator](), parseInt);
46    const l2 = buildList(splitWords(yield)[Symbol.iterator](), parseInt);
47    const res = merge(l1, l2);
48    console.log(Array.from(formatList(res)).join(" "));
49}
50
51class EOFError extends Error {}
52{
53    const gen = main();
54    const next = (line?: string) => gen.next(line ?? "").done && process.exit();
55    let buf = "";
56    next();
57    process.stdin.setEncoding("utf8");
58    process.stdin.on("data", (data) => {
59        const lines = (buf + data).split("\n");
60        buf = lines.pop() ?? "";
61        lines.forEach(next);
62    });
63    process.stdin.on("end", () => {
64        buf && next(buf);
65        gen.throw(new EOFError());
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
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
Favorite (idle)