Add 1 to a Number as Linked List

Add 1 to a Number as Linked List stores a number one digit per node, most significant digit first, and asks you to add 1 to it. The twist: the carry from +1 flows from the last node toward the first, but a singly linked list only lets you walk forward. The clean fix is to flip the list, add, and flip it back.

The slow way first

The obvious idea: walk to the end, convert the digits into an integer, add 1, then rebuild the list from the new digits. That works for small inputs, but it overflows the moment the number has more digits than a machine integer holds — and interviewers pick this problem precisely to see whether you can add digit-by-digit without ever forming the whole number.

The real obstacle is direction. Addition starts at the ones place (the tail), but our pointers only move head-to-tail. We need the least significant digit to come first.

The idea: reverse, add the carry, reverse back

Flip the list so the ones digit is at the head. Now walk forward carrying a running carry that starts at 1 (the +1 we are adding). At each node compute total = digit + carry, store total % 10 back into the node, and keep total // 10 as the carry for the next node. If a carry is still left after the last node, prepend a new node holding it. Finally reverse the list back to its original order.

The key insight: a carry only ever moves one direction — from a lower place toward a higher place. Reversing the list aligns that direction with the way we can actually walk, so a single forward pass does the whole addition.

Walk through it

Step through the animation. We start with 1 -> 9 -> 9 (the number 199). After reversing, the head is the ones digit, so the row reads 9 -> 9 -> 1. The curr pointer sweeps left while carry rides along: 9 + 1 = 10 keeps a 0 and carries 1, the next 9 + 1 = 10 keeps another 0 and carries 1, and 1 + 1 = 2 finally absorbs the carry (carry becomes 0). With no carry left we skip the prepend, reverse back, and read off 2 -> 0 -> 0.

Pseudocode

reverse the list                       # ones digit becomes the head
carry = 1                              # the +1 we are adding
for each node curr from head:
    total = curr.value + carry
    curr.value = total mod 10           # digit we keep here
    carry = total div 10                # what spills into the next node
if carry > 0:
    prepend a new node holding carry    # e.g. 999 + 1 -> a leading 1
reverse the list back                  # restore most-significant-first
return the head

The Python solution

def add_one(head):
    head = reverse(head)
    carry = 1
    curr = head
    while curr:
        total = curr.val + carry
        curr.val = total % 10
        carry = total // 10
        curr = curr.next
    if carry:
        head = prepend(head, carry)
    head = reverse(head)
    return head

• reverse(head) flips the list so the ones digit leads — now a forward walk matches the carry direction.
• carry = 1 seeds the loop: adding 1 is just an initial carry of 1.
• total = curr.val + carry is the digit plus whatever spilled in from the previous node.
• curr.val = total % 10 keeps the last digit; carry = total // 10 is what spills onward (always 0 or 1 here).
• Lines 10-11 handle the leftover carry: if it survives the last node (like 999 + 1), prepend a node for it.
• The final reverse restores the original most-significant-first order before we return the head.

Complexity

We touch each node a constant number of times, so the work is O(n), and we mutate the list in place (plus at most one prepended node), so the extra space is O(1). Unlike the convert-to-integer approach, this never builds the whole number, so it handles arbitrarily long lists.

When this pattern shows up

Practice