Add Two Numbers — LeetCode #2 (Medium)

The Problem

Add two numbers whose digits are stored as nodes of two linked lists in reverse order, and return the sum as a linked list.

Example

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

Output: [7,0,8]

342 + 465 = 807.

Constraints

Each list has 1 to 100 nodes
Each node value is a single digit, 0 to 9
No leading zeros except the number 0 itself

The Key Insight

Now think about how you'd add by hand. You don't glue the digits into one number first. You go column by column. So what if we do exactly that here? Take the two matching digits, add just those, write down one result, and move on.

That's the move. Column-by-column addition. And since the digits are already reversed, the ones column comes first. That lines up perfectly. One catch. Four plus six is ten. Ten doesn't fit in a single digit slot, so we keep the last digit and carry the one forward.

That carry is the only memory we need. It's just one small number, handed from each column to the next one. Watch out for one mistake. You might think to stop once both lists run out. But if the last column carried a one, you still owe one more digit.

Why It Works

Notice what we never did. We never built those big numbers. Each digit got touched once, and the carry held the only memory we needed.

Walking Through It

Let's run it. Carry starts at zero. We also keep a fake starting node, so attaching the very first digit needs no special handling. First column. Two plus five is seven, plus a carry of zero. Nothing spills over, so we attach a node holding seven.

Next column. Four plus six is ten. Ten won't fit in one digit slot, so something has to give. We keep the last digit, which is zero, and attach a node holding zero. The leftover one becomes the carry into the next column.

Last column. Three plus four is seven, plus the carried one, that makes eight. We attach a node holding eight. Both lists are empty now, and the carry is zero. There's nothing left to add, so we stop.

Drop the fake node, and the answer starts at seven. Read it out as a whole, eight hundred seven. Correct.

Complexity

We walk each list one time, so the time grows with the longer list. The answer holds one node per digit, so the memory grows the same way.

The Code

Same logic, now in Python. We make a fake starting node, a pointer to build from, and set the carry to zero. The loop keeps running while either list still has a digit, or there's a leftover carry. That last part catches the final one.

Inside, we read each digit. If a list has already run out, we treat its digit as zero, so two different lengths just work. We add the two digits and the carry. The new carry is whatever spilled past ten, and the new node takes the last digit.

Then we step all the pointers forward. When the loop ends, we hand back the list that starts right after the fake node.

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode()
        curr = dummy
        carry = 0
        while l1 or l2 or carry:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            total = x + y + carry
            carry = total // 10
            curr.next = ListNode(total % 10)
            curr = curr.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummy.next

Wrap-up

And that's it. Column by column, carry the one. It's the same addition you learned in grade school, just walking a list.

📺 Watch the full walkthrough on YouTube: https://youtu.be/wz9Dhg5LYqI

推荐订阅源

DEV Community