Getting everything ready for you…

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

0s

Practice › Linked List

Add One to a Linked List

Medium · Linked List · Asked at Amazon, Microsoft, Samsung

A non-negative number is stored with one digit per node, most significant digit first, and no leading zeros (except the number 0 itself). Add 1 to the number and print the resulting digits.

Input

First line: n. Second line: the n digits.

Output

The digits of the result, space-separated.

Constraints

Reverse, add with carry, reverse back. Or recurse to the end and pass the carry back up. A new head is needed when all digits are 9.

Example 1

Input

3
1 2 3

Output

1 2 4

Example 2

Input

3
9 9 9

Output

1 0 0 0

Hints

  1. Adding starts at the least significant digit, which is the tail. Reverse the list first.
  2. Add 1 with a carry while walking, reverse back, and add a new head node if a carry is left (e.g. 999 → 1000).

Approach

Reverse the list so the units digit comes first. Walk it with carry = 1: sum = digit + carry, store sum % 10, carry = sum / 10; stop early when the carry becomes 0. Reverse back. If the carry is still 1, prepend a node with value 1. The number can have 10^5 digits, so never convert it to an integer.

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

Solution

C++ solution

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

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

Node *reverseList(Node *h) {
    Node *prev = nullptr;
    while (h) {
        Node *nx = h->next;
        h->next = prev;
        prev = h;
        h = nx;
    }
    return prev;
}

int main() {
    int n;
    cin >> n;
    Node dummy(0), *t = &dummy;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        t = t->next = new Node(x);
    }
    Node *head = reverseList(dummy.next);
    int carry = 1;
    for (Node *p = head; p && carry; p = p->next) {
        int s = p->val + carry;
        p->val = s % 10;
        carry = s / 10;
    }
    head = reverseList(head);
    if (carry) {
        Node *nh = new Node(1);
        nh->next = head;
        head = nh;
    }
    for (Node *p = head; 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 reverse(h):
    prev = None
    while h:
        h.next, prev, h = prev, h, h.next
    return prev


data = list(map(int, sys.stdin.read().split()))
dummy = tail = Node(0)
for v in data[1 : 1 + data[0]]:
    tail.next = Node(v)
    tail = tail.next
head = reverse(dummy.next)
carry, p = 1, head
while p and carry:
    s = p.val + carry
    p.val, carry = s % 10, s // 10
    p = p.next
head = reverse(head)
if carry:
    nh = Node(1)
    nh.next = head
    head = nh
out = []
while head:
    out.append(head.val)
    head = head.next
print(*out)

Java solution

import java.util.*;
import java.io.*;

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

    static Node reverse(Node h) {
        Node prev = null;
        while (h != null) {
            Node nx = h.next;
            h.next = prev;
            prev = h;
            h = nx;
        }
        return prev;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Node dummy = new Node(0), t = dummy;
        for (int i = 0; i < n; i++) t = t.next = new Node(Integer.parseInt(st.nextToken()));
        Node head = reverse(dummy.next);
        int carry = 1;
        for (Node p = head; p != null && carry > 0; p = p.next) {
            int s = p.val + carry;
            p.val = s % 10;
            carry = s / 10;
        }
        head = reverse(head);
        if (carry > 0) {
            Node nh = new Node(1);
            nh.next = head;
            head = nh;
        }
        StringBuilder sb = new StringBuilder();
        for (Node p = head; p != null; p = p.next) sb.append(p.val).append(p.next != null ? " " : "");
        System.out.println(sb);
    }
}

Solve Add One to a Linked List online · All practice problems