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
- 1 ≤ n, m ≤ 10^5
- -10^9 ≤ values ≤ 10^9
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
- Put a dummy node in front of the result, and keep a tail pointer.
- 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);
}
}