Add 1 to a number represented as a linked list

Medium

Problem

A non-negative number is stored one digit per node, most significant digit first. Add 1 to it and return the resulting list.

Example 1

Input:  4 → 5 → 6
Output: 4 → 5 → 7

Example 2

Input:  9 → 9 → 9
Output: 1 → 0 → 0 → 0

Also asked as: Add “1” to a number represented as a Linked List

Test cases

Case 1

Input:    [4,5,6]
Expected: [4,5,7]

Case 2

Input:    [9,9,9]
Expected: [1,0,0,0]

Case 3

Input:    [1,2,9]
Expected: [1,3,0]

Case 4

Input:    [0]
Expected: [1]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Reverse, add carry, reverse back

Time O(n)Space O(1)

Reverse so the least-significant digit is first, add 1 propagating carry, reverse again.

function addOne(head) {
const rev = (h) => { let p = null; while (h) { const n = h.next; h.next = p; p = h; h = n; } return p; };
head = rev(head);
let cur = head, carry = 1;
while (cur && carry) {
const sum = cur.val + carry;
cur.val = sum % 10;
carry = sum >= 10 ? 1 : 0;
if (carry && !cur.next) { cur.next = { val: 0, next: null }; }
cur = cur.next;
}
return rev(head);
}