LeetCode 445: Add Two Numbers II Solution in Python – A Step-by-Step Guide

What Is LeetCode 445: Add Two Numbers II?

In LeetCode 445: Add Two Numbers II, you’re given two linked lists representing non-negative integers, with digits stored from most significant (head) to least significant (tail)—e.g., 7→2→4 is 724. Your task is to add them and return a new linked list with the sum, also in the same order (e.g., 1→2→9→1 for 1291). Unlike its sibling, LeetCode 2, you can’t reverse the lists directly because the problem implies working from the front. For example, 7→2→4 + 5→6→7 = 1→2→9→1. It’s like adding numbers on paper, left to right, with a carry twist.

Problem Statement

• Input: l1 (ListNode)—first number; l2 (ListNode)—second number.
• Output: ListNode—sum as a linked list.
• Rules:
• Digits are most significant first (head).
• No leading zeros in input (except 0 itself).
• Return sum in same order.

Constraints

• Number of nodes in each list: [1, 100].
• 0 <= node.val <= 9.
• No leading zeros (unless the number is 0).

Examples to Get Us Started

• Input: l1 = 7->2->4->3, l2 = 5->6->4
• Output: 7->8->0->7 (7243 + 564 = 7807).
• Input: l1 = 2->4->3, l2 = 5->6->4
• Output: 8->0->7 (243 + 564 = 807).
• Input: l1 = 0, l2 = 0
• Output: 0.

Understanding the Problem: Adding from the Top

To solve LeetCode 445: Add Two Numbers II in Python, we need to add two numbers from most to least significant digit, producing a result in the same order. Adding from the left means handling carries after the fact, unlike the right-to-left addition in LeetCode 2. A naive approach—converting to integers and back—works but risks overflow for large lists. We’ll explore:

• Best Solution (Stack-Based): O(n) time, O(n) space—clever and list-preserving.
• Alternative Solution (Reverse and Add): O(n) time, O(1) space (if reversing in-place)—simpler but modifies input.

Let’s dive into the stack-based solution—it’s the scroll-friendly way to go.

Best Solution: Stack-Based Addition

Why This Is the Best Solution

The stack-based approach is the top pick because it’s O(n) time and O(n) space, elegantly handling addition from left to right without reversing the original lists. It uses stacks to store digits, pop them from the tail (least significant), add with carry, and build the result from right to left, then adjusts to most-significant-first order. It’s like stacking the digits on plates, adding from the bottom, and flipping the pile—smooth and efficient!

How It Works

Here’s the strategy:

• Step 1: Push all digits from both lists onto separate stacks.
• Step 2: Pop from both stacks, add digits with carry:
• Build a new linked list from least to most significant.
• Step 3: Handle any remaining carry.
• Step 4: Return the head of the result list.
• Why It Works:
• Stacks reverse the order naturally.
• Adding from the tail mimics standard addition.
• Final list is constructed correctly.

Step-by-Step Example

Example: l1 = 7->2->4->3, l2 = 5->6->4

• Stacks:
• l1_stack: [7, 2, 4, 3] (top: 3).
• l2_stack: [5, 6, 4] (top: 4).
• Add:
• 3 + 4 = 7, carry = 0, result = 7.
• 4 + 6 = 10, carry = 1, result = 0->7.
• 2 + 5 + 1 = 8, carry = 0, result = 8->0->7.
• 7 + 0 = 7, carry = 0, result = 7->8->0->7.
• Result: 7->8->0->7 (7807).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy code# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # Step 1: Push digits to stacks
        stack1, stack2 = [], []
        while l1:
            stack1.append(l1.val)
            l1 = l1.next
        while l2:
            stack2.append(l2.val)
            l2 = l2.next

        # Step 2: Add from stacks with carry
        carry = 0
        result = None

        while stack1 or stack2 or carry:
            x = stack1.pop() if stack1 else 0
            y = stack2.pop() if stack2 else 0
            total = x + y + carry
            carry = total // 10
            digit = total % 10

            # Build result list (right to left)
            new_node = ListNode(digit)
            new_node.next = result
            result = new_node

        return result

• Line 11-16: Push digits to stacks (e.g., 7->2->4->3 → [7, 2, 4, 3]).
• Line 19-20: Initialize carry and result.
• Line 22-30: Add digits:
• Pop x, y (or 0 if stack empty).
• Compute total, carry, digit.
• Create new node, prepend to result.
• Line 32: Return head.
• Time Complexity: O(n)—one pass per list, one for addition.
• Space Complexity: O(n)—stacks.

It’s like a digital abacus with a stack twist!

Alternative Solution: Reverse and Add

Why an Alternative Approach?

The reverse-and-add method reverses both lists, adds them like LeetCode 2, then reverses the result—O(n) time, O(1) space if reversing in-place. It’s simpler but modifies input, which the problem discourages. It’s like flipping the scrolls, adding normally, and flipping back—intuitive but less elegant!

How It Works

• Step 1: Reverse l1 and l2.
• Step 2: Add reversed lists with carry.
• Step 3: Reverse the result.
• Step 4: Return head.

Step-by-Step Example

Example: l1 = 7->2->4->3, l2 = 5->6->4

• Reverse:
• l1: 3->4->2->7.
• l2: 4->6->5.
• Add:
• 3 + 4 = 7, 4 + 6 = 10 (carry 1), 2 + 5 + 1 = 8, 7 = 7.
• Result: 7->0->8->7.
• Reverse: 7->8->0->7.
• Result: 7->8->0->7.

Code for Reverse and Add

Copy codeclass Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # Reverse both lists
        l1 = self.reverseList(l1)
        l2 = self.reverseList(l2)

        # Add like LeetCode 2
        dummy = ListNode(0)
        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

        # Reverse result
        return self.reverseList(dummy.next)

• Line 2-10: Reverse helper.
• Line 15-29: Reverse, add, reverse back.
• Time Complexity: O(n)—three passes.
• Space Complexity: O(1)—in-place reversal.

It’s a flip-and-add classic!

Comparing the Two Solutions

• Stack-Based (Best):
• Pros: O(n), preserves input, elegant.
• Cons: O(n) space.
• Reverse and Add (Alternative):
• Pros: O(n), O(1) space, familiar.
• Cons: Modifies input.

Stack wins for compliance.

Edge Cases and More Examples

• Input: l1=0, l2=0 → 0.
• Input: l1=1, l2=9->9 → 1->0->0.
• Input: l1=5, l2=5 → 1->0.

Both handle these well.

Complexity Recap

• Stack-Based: Time O(n), Space O(n).
• Reverse: Time O(n), Space O(1).

Stack’s the champ here.

Key Takeaways

• Stack: Add without flipping.
• Reverse: Flip and add.
• Python Tip: Stacks simplify—see [Python Basics](/python/basics).

Final Thoughts: Sum Those Scrolls

LeetCode 445: Add Two Numbers II in Python is a linked list math adventure. Stack-based addition is your scroll-preserving hero, while reversing offers a familiar twist. Want more list fun? Try LeetCode 2: Add Two Numbers or LeetCode 206: Reverse Linked List. Ready to add some digits? Head to Solve LeetCode 445 on LeetCode and sum it up today—your coding skills are adding up!