Add two numbers represented by linked lists

The problem, simply

You get two linked lists. Each one is a number, one digit per box, with the biggest digit at the head. So 9 -> 9 -> 6 is 996 and 2 -> 7 is 27.

Build a new list that holds their sum, also biggest digit first. For 996 + 27 the answer is 1 -> 0 -> 2 -> 3. The numbers can be hundreds of digits long, far too big for an int or a long.

A story to remember it

Picture it

Examples

Way 1: the simple way

The first idea, turning each list into a long and adding, breaks for long numbers: a long holds only about 19 digits. So do it digit by digit, and use two stacks of plates to read the digits from the right.

1. Walk list a and push each digit onto stack 1. Do the same for b and stack 2. The ones digits end up on top.
2. While a stack has plates or the carry is not 0: pop the top of each stack, add them and the carry.
3. Make a box with sum % 10 and put it in front of the answer. The new carry is sum / 10.

class Solution {
    public ListNode addTwoLists(ListNode a, ListNode b) {
        Deque<Integer> s1 = new ArrayDeque<>(), s2 = new ArrayDeque<>();
        for (ListNode p = a; p != null; p = p.next) s1.push(p.val);
        for (ListNode p = b; p != null; p = p.next) s2.push(p.val);

        ListNode ans = null;
        int carry = 0;
        while (!s1.isEmpty() || !s2.isEmpty() || carry > 0) {
            int sum = carry;
            if (!s1.isEmpty()) sum += s1.pop();   // ones digit comes off first
            if (!s2.isEmpty()) sum += s2.pop();
            ListNode box = new ListNode(sum % 10);
            box.next = ans;                       // put the new digit in front
            ans = box;
            carry = sum / 10;
        }
        while (ans != null && ans.next != null && ans.val == 0) ans = ans.next; // no leading zeros
        return ans;
    }
}

How long it takes: every digit is pushed once and popped once, O(m + n). Extra room: two stacks as long as the lists, O(m + n), on top of the answer list.

Way 2: the clever way

The stacks were only there to read from the right. We can get the same thing for free by flipping each chain with the three finger reversal.

1. Reverse a and reverse b. Now both start at the ones digit.
2. Walk both together with a carry. Missing digits count as 0.
3. For each column, make a box with sum % 10 and put it in front of the answer, so the answer comes out biggest digit first with no third reversal.
4. Strip leading zeros. If the caller still needs the inputs, flip them back.

class Solution {
    public ListNode addTwoLists(ListNode a, ListNode b) {
        ListNode ra = reverse(a), rb = reverse(b);   // ones digit first
        ListNode p = ra, q = rb, ans = null;
        int carry = 0;
        while (p != null || q != null || carry > 0) {
            int sum = carry;
            if (p != null) { sum += p.val; p = p.next; }
            if (q != null) { sum += q.val; q = q.next; }
            ListNode box = new ListNode(sum % 10);
            box.next = ans;                          // new digit goes in front
            ans = box;
            carry = sum / 10;
        }
        reverse(ra);                                 // give the caller their lists back
        reverse(rb);
        while (ans != null && ans.next != null && ans.val == 0) ans = ans.next;
        return ans;
    }

    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: each list is flipped twice and walked once, O(m + n). Extra room: only a few fingers, O(1), apart from the answer list that we must return anyway.

Watch out for

• Converting to int or long overflows once the numbers pass about 19 digits. Never do it in an interview.
• Lining up the wrong ends. The ones digits are at the tails, so lists of different lengths must be matched from the right, not from the head.
• Leading zeros. Strip them, but keep one box when the sum is 0.
• Forgetting that reversing changes the caller's lists. Flip them back, or say clearly that you modify the input.

What interviewers ask next

• What if the digits are stored ones digit first (LeetCode 2)? Then no flipping is needed: walk both heads together with a carry and append to a tail with a dummy head.
• Can you do it without changing the inputs and without stacks? Yes, with recursion: pad the shorter list with zeros in front, recurse to the end, and return the carry on the way back. That costs O(m + n) call stack.
• Subtract the two numbers instead? Same shape: flip, subtract column by column with a borrow, then strip leading zeros. First compare lengths to know which number is bigger.
• Multiply them? See the multiply problem: do it like school multiplication, or work modulo a big prime if only the remainder is asked.

Remember this

Grown-up words: the boxes are nodes, the column overflow is the carry, the stacks of plates are a stack (LIFO), flipping is in place list reversal, and putting a box in front is inserting at the head.