Add Two Numbers

MediumLinked listsLeetCode 2 ↗World 1-11

0:00 / 0:00

Two numbers stored as reversed linked lists: walk both at once, add digit by digit like on paper, and carry the 1 into the next node.

▼

The problem

LeetCode 2 (Medium). Two non-empty linked lists hold two non-negative integers, one digit per node, with the digits in reverse order (the ones digit first). Add the two numbers and return the sum as a linked list in the same form.

Examples (LeetCode's): l1 = [2,4,3], l2 = [5,6,4] → [7,0,8] (342 + 465 = 807, the walkthrough), [0] + [0] → [0], and [9,9,9,9,9,9,9] + [9,9,9,9] → [8,9,9,9,0,0,0,1] (9999999 + 9999 = 10009998: the carry ripples through and the last carry adds a node).

TRY IT ON LEETCODE ▶

The solution

def addTwoNumbers(list1, list2):
    dummy = tail = ListNode()
    carry = 0
    while list1 or list2 or carry:
        a = list1.val if list1 else 0
        b = list2.val if list2 else 0
        total = a + b + carry
        tail.next = ListNode(total % 10)
        carry = total // 10
        tail = tail.next
        list1 = list1.next if list1 else None
        list2 = list2.next if list2 else None
    return dummy.next

Transcript

Add Two Numbers. Two linked lists each hold a number, one digit per node, in reverse: the ones digit comes first. Add them and return the sum as a list in the same form.

Take two, four, three and five, six, four. Backward, that's three hundred forty-two plus four hundred sixty-five: eight hundred seven. So return seven, zero, eight. Zero plus zero is zero.

The easy way: turn each list into an integer, add, and split the sum back into nodes. But a list can hold a hundred digits, and a sixty-four-bit integer overflows past nineteen.

Instead, add like in school, column by column from the ones digit, which is right where both lists start. Each column adds two digits plus a carry: keep the sum mod ten, carry the tens. It's Plus One's carry, on two lists.

In code, a dummy node anchors the answer and carry starts at zero. Loop while either list or the carry remains; a missing node counts as zero. Append the total mod ten, carry the total divided by ten, step forward, and return dummy dot next.

Two plus five is seven, no carry. Four plus six is ten: write zero, carry one. Three plus four plus one is eight: seven, zero, eight. With seven nines plus four nines, the carry ripples through, and the last one grows a new node.

Each node is visited once: order max of m and n time, and constant extra space beyond the answer.

Line up the digits, add each column, carry the one. That's Add Two Numbers.