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
- 1 ≤ n ≤ 10^5
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
- Adding starts at the least significant digit, which is the tail. Reverse the list first.
- 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