Add 1 to a number represented as a Linked List

The problem, simply

A number is stored in a linked list, one digit per box. The first box holds the biggest digit, so 1 -> 2 -> 3 means 123.

Add 1 to the number and give back the head of the list that shows the answer. If the number gets one digit longer (999 becomes 1000), you need a new box at the front.

A story to remember it

Picture it

Examples

Way 1: the simple way

We add numbers on paper from the right. The chain only lets us walk from the left. So turn the chain around, add like on paper, and turn it back.

1. Reverse the list, so the smallest digit is first.
2. Carry starts at 1. Walk the list: add the carry to the box, keep the last digit, pass the rest along as the new carry.
3. If a carry is still left at the end, hang a new box with 1 on the end.
4. Reverse the list again and return the new head.

class Solution {
    public ListNode addOne(ListNode head) {
        head = reverse(head);              // smallest digit first
        ListNode curr = head;
        int carry = 1;                     // the 1 we want to add
        while (curr != null && carry > 0) {
            int sum = curr.val + carry;
            curr.val = sum % 10;           // keep the last digit
            carry = sum / 10;              // pass the rest along
            if (curr.next == null && carry > 0) {
                curr.next = new ListNode(carry);   // grow by one box
                carry = 0;
            }
            curr = curr.next;
        }
        return reverse(head);              // turn it back
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

How long it takes: three walks over the list (flip, add, flip), so O(n). Extra room: a few fingers, O(1). It works, but it rewires every arrow twice and changes the list even when only one digit moves.

Way 2: the clever way

Think about the odometer. Only one digit really goes up: the last one that is not a 9. Everything after it is a 9 and rolls to 0. So we never need to walk backwards.

1. Walk the list once. Every time you see a digit that is not 9, put the notNine finger on it.
2. If notNine was never set, every digit is 9. Make a new head box with 0 in front and point notNine at it.
3. Add 1 to the notNine box.
4. Walk from the box after notNine to the end and set every digit to 0.

class Solution {
    public ListNode addOne(ListNode head) {
        ListNode notNine = null;
        for (ListNode curr = head; curr != null; curr = curr.next) {
            if (curr.val != 9) notNine = curr;   // the last wheel that can go up
        }
        if (notNine == null) {                   // all nines: a new wheel on the left
            ListNode front = new ListNode(0);
            front.next = head;
            head = front;
            notNine = front;
        }
        notNine.val += 1;
        for (ListNode curr = notNine.next; curr != null; curr = curr.next) {
            curr.val = 0;                        // every 9 after it rolls to 0
        }
        return head;
    }
}

How long it takes: one walk to find notNine and at most one more walk to zero the 9s, O(n). Extra room: one finger and maybe one new box, O(1). No arrows are rewired.

Watch out for

• Returning the old head after you added a new box in front. Return the new head.
• Leading zeros: if the input can be 0 -> 0 -> 9, ask if the answer should keep them. Most judges give inputs without leading zeros.
• In Way 1, forgetting the second reverse leaves the answer backwards.
• An empty list. Decide with the interviewer: usually it is treated as 0, so the answer is a single box with 1.

What interviewers ask next

• Can you do it with recursion? Yes. Go to the end first, return a carry of 1 from past the last box, and on the way back each box adds the carry it gets. If the head still returns a carry, add a new box. That costs O(n) stack space.
• What if the digits are stored smallest first? Then no trick is needed. Start at the head with carry 1 and stop as soon as the carry is 0.
• Add any number k instead of 1? Then the carry can be bigger than 1, so the last non 9 trick no longer works. Reverse, add with carry, reverse back.
• Can you do it in one pass? You can keep notNine while walking, but the zeroing walk is still needed. Both walks are O(n), and you cannot do better than reading every digit once.

Remember this

Grown-up words: the odometer wheels are digits, the nudge to the left is the carry, the boxes are nodes, the head holds the most significant digit, and the notNine finger is a pointer to the rightmost non 9 node.