Practice › Linked List
Add Two Numbers as Lists
Medium · Linked List · Asked at Amazon, Microsoft, Google, Adobe, Flipkart
Two non-negative numbers are stored as linked lists with digits in reverse order (head = ones digit). Add them and print the result list in the same reverse order.
Input
Line 1: n. Line 2: n digits. Line 3: m. Line 4: m digits.
Output
The digits of the sum in reverse order, space-separated.
Constraints
- 1 ≤ n, m ≤ 100
- No leading zeros except the number 0 itself
Example 1
Input
3 2 4 3 3 5 6 4
Output
7 0 8
Example 2
Input
1 0 1 0
Output
0
Hints
- The ones digits come first — exactly the order in which you add numbers by hand.
- Walk both lists together with a carry. Keep going while either list has nodes or the carry is non-zero.
Approach
Like column addition. At each step, sum = (a ? a.val : 0) + (b ? b.val : 0) + carry. Append a node with sum % 10 and set carry = sum / 10. Keep going until both lists are finished and the carry is 0; the last check adds a final 1 for cases like 5 + 5 = 10. The numbers can have 100 digits, so converting them to built-in integers would overflow in C++ and Java.
Complexity: O(max(n, m)) time · O(max(n, m)) space for the result
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
Node *next;
Node(int v) : val(v), next(nullptr) {}
};
Node *readList() {
int n;
cin >> n;
Node dummy(0), *tail = &dummy;
for (int i = 0; i < n; i++) {
int v;
cin >> v;
tail = tail->next = new Node(v);
}
return dummy.next;
}
int main() {
Node *a = readList(), *b = readList();
Node dummy(0), *tail = &dummy;
int carry = 0;
while (a || b || carry) {
int sum = carry + (a ? a->val : 0) + (b ? b->val : 0);
tail = tail->next = new Node(sum % 10);
carry = sum / 10;
if (a) a = a->next;
if (b) b = b->next;
}
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, nxt=None):
self.val, self.next = val, nxt
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a = build(data[1 : n + 1])
m = data[n + 1]
b = build(data[n + 2 : n + 2 + m])
dummy = tail = Node(0)
carry = 0
while a or b or carry:
total = carry + (a.val if a else 0) + (b.val if b else 0)
tail.next = Node(total % 10)
tail = tail.next
carry = total // 10
a = a.next if a else None
b = b.next if b else None
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 {
int val;
Node next;
Node(int v) { val = v; }
}
static Node readList(Scanner sc) {
int n = sc.nextInt();
Node dummy = new Node(0), tail = dummy;
for (int i = 0; i < n; i++) tail = tail.next = new Node(sc.nextInt());
return dummy.next;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Node a = readList(sc), b = readList(sc);
Node dummy = new Node(0), tail = dummy;
int carry = 0;
while (a != null || b != null || carry != 0) {
int sum = carry + (a != null ? a.val : 0) + (b != null ? b.val : 0);
tail = tail.next = new Node(sum % 10);
carry = sum / 10;
if (a != null) a = a.next;
if (b != null) b = b.next;
}
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 Add Two Numbers as Lists online · All practice problems