MediumLinked ListMathRecursion

Add Two Numbers

1 approach, code in every language

You are given two non-empty linked lists that each represent a non-negative integer. The digits are stored in reverse order, so the head of the list holds the least significant digit, and every node contains exactly one digit.

Add the two numbers together and return the result as a linked list, using the same reverse-order digit layout. You may assume that neither number has any leading zeros, except for the number zero itself.

Example 1

Input: l1 = [2,4,3], l2 = [5,6,4]

Output: [7,0,8]

The lists encode 342 and 465. Their sum is 807, which written back in reverse-digit order is 7 -> 0 -> 8.

Example 2

Input: l1 = [9,9,9], l2 = [1]

Output: [0,0,0,1]

This is 999 + 1 = 1000. The carry ripples through every digit and produces a new most significant node, giving 0 -> 0 -> 0 -> 1.

Constraints

The number of nodes in each list is in the range [1, 100].
0 <= Node.val <= 9
Each list represents a number without leading zeros (except the value 0).
The combined result can exceed 10^30, so process it digit by digit rather than as a native integer.

Dummy Head with Running Carry

Walk both lists in lockstep, adding digits plus a carry and building the result behind a dummy head.

Loading animation…

Intuition

This is grade-school addition expressed on linked lists. Because the digits are already stored least-significant-first, we can add left to right exactly the way we add columns of numbers by hand. At each step we combine the current digit from each list plus any carry from the previous column. The units digit of that sum becomes a new node, and anything that overflows past nine becomes the carry into the next column. A dummy head lets us append nodes without special-casing the very first one, and we keep going until both lists are exhausted and no carry remains.

Algorithm walkthrough

1Create a dummy node and a tail pointer that starts at the dummy; initialize carry to 0.
2Loop while either list still has nodes or the carry is non-zero.
3Read the current value from each list (treating a missing node as 0), then compute sum = digit1 + digit2 + carry.
4Append a new node holding sum % 10 to the tail, and set carry = sum / 10 (integer division).
5Advance the tail and advance each list pointer that still has a node.
6After the loop, return dummy.next, which is the head of the summed list.

Implementation

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        tail = dummy
        carry = 0
        while l1 or l2 or carry:
            digit1 = l1.val if l1 else 0
            digit2 = l2.val if l2 else 0
            total = digit1 + digit2 + carry
            carry = total // 10
            tail.next = ListNode(total % 10)
            tail = tail.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        return dummy.next

Time

O(max(m, n))

Space

O(max(m, n))

m and n are the lengths of the two lists. We touch each node once and allocate one output node per digit, plus possibly one extra node for a final carry.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Odometer Tape Sum is our own problem on the technique behind Add Two Numbers: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free