Getting everything ready for you…

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

0s

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

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

  1. The ones digits come first — exactly the order in which you add numbers by hand.
  2. 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