Add 1 to a number represented as a linked list
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]
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);}