Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Linked List

Merge Two Sorted Lists

Easy · Linked List · Asked at Amazon, Microsoft, Google, Apple, TCS

Both linked lists are sorted in non-decreasing order. Merge them into one sorted list by relinking the nodes (no new nodes) and print it.

Input

First line: n. Second line: the first list. Third line: m. Fourth line: the second list.

Output

The merged list, space-separated.

Constraints

A dummy head node removes the special case for the first node.

Example 1

Input

3
1 2 4
3
1 3 4

Output

1 1 2 3 4 4

Example 2

Input

1
5
2
1 2

Output

1 2 5

Hints

  1. Put a dummy node in front of the result, and keep a tail pointer.
  2. Repeatedly attach the smaller of the two current heads to the tail; when one list ends, attach the rest of the other.

Approach

Two pointers walk the lists. At each step the smaller head is linked after tail and its list advances. Once one list is exhausted, the other is already sorted, so link it in one step. The dummy node avoids special-casing the first node; the answer is dummy.next. No new nodes are created.

Complexity: O(n + m) time · O(1) extra space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long val;
    Node *next = nullptr;
    Node(long long v) : val(v) {}
};

Node *readList(int n) {
    Node dummy(0), *t = &dummy;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        t = t->next = new Node(x);
    }
    return dummy.next;
}

int main() {
    int n, m;
    cin >> n;
    Node *a = readList(n);
    cin >> m;
    Node *b = readList(m);
    Node dummy(0), *tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) tail->next = a, a = a->next;
        else tail->next = b, b = b->next;
        tail = tail->next;
    }
    tail->next = a ? a : b;
    for (Node *p = dummy.next; p; p = p->next) cout << p->val << (p->next ? " " : "\n");
    return 0;
}

Python solution

import sys


class Node:
    def __init__(self, val):
        self.val, self.next = val, None


def build(vals):
    dummy = tail = Node(0)
    for v in vals:
        tail.next = Node(v)
        tail = tail.next
    return dummy.next


data = list(map(int, sys.stdin.read().split()))
n = data[0]
a = build(data[1 : 1 + n])
m = data[1 + n]
b = build(data[2 + n : 2 + n + m])
dummy = tail = Node(0)
while a and b:
    if a.val <= b.val:
        tail.next, a = a, a.next
    else:
        tail.next, b = b, b.next
    tail = tail.next
tail.next = a or b
out, p = [], dummy.next
while p:
    out.append(p.val)
    p = p.next
print(*out)

Java solution

import java.util.*;

public class Main {
    static class Node {
        long val;
        Node next;
        Node(long v) { val = v; }
    }

    static Node readList(Scanner sc, int n) {
        Node dummy = new Node(0), t = dummy;
        for (int i = 0; i < n; i++) t = t.next = new Node(sc.nextLong());
        return dummy.next;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Node a = readList(sc, sc.nextInt());
        Node b = readList(sc, sc.nextInt());
        Node dummy = new Node(0), tail = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = a != null ? a : b;
        StringBuilder sb = new StringBuilder();
        for (Node p = dummy.next; p != null; p = p.next) sb.append(p.val).append(p.next != null ? " " : "");
        System.out.println(sb);
    }
}

Solve Merge Two Sorted Lists online · All practice problems