Amazon Online Assessment (OA) - Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the given two 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: 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)))
34

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

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

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Introduction

DFS on Tree

Binary Search Tree

Combinatorial Search

Memoization

Pruning

Dedup

Additional Practices

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Sequence

Grid

Dynamic number of subproblems

Partition

Interval

Two Sequences

Game Theory

0-1 Knapsack

Bitmask

Tree

Introduction

Generalized

Binary Search

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Line Sweep

Tree Traversal without Recursion

Greedy

Composite Patterns

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Amazon Online Assessment (OA) - Merge Two Sorted Lists

Examples:

Example1:

Input: l1 = [1,2,4], l2 = [1,3,4]

Example 2:

Input: l1 = [], l2 = []

Example 3:

Input: l1 = [], l2 = [0]

Constraints:

Try it yourself

Solution

Input: `l1 = [1,2,4]`, `l2 = [1,3,4]`

Input: `l1 = []`, `l2 = []`

Input: `l1 = []`, `l2 = [0]`