Add Two Numbers | Leetcode 2

Welcome to our deep dive on Add Two Numbers (Leetcode 2). This problem tests your ability to cleanly traverse multiple Linked Lists simultaneously while managing mathematical carry values.

Problem Statement

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example: l1 = [2,4,3], l2 = [5,6,4] => Output: [7,0,8] (Explanation: 342 + 465 = 807)

Approach: Elementary Math Simulation O(max(M,N))

Because the linked lists explicitly store the numbers in reverse order, the very first nodes of each list represent the "ones" place! This is incredibly convenient. We can literally just simulate grade school addition starting from the ones column and propagating a "carry" value leftwards.

1. Create a dummy head node to safely anchor our new resulting Linked List.
2. Maintain a carry integer variable, initially set to 0.
3. Loop cleanly while l1 is not null, l2 is not null, OR carry is greater than 0.
4. Extract the values. If l1 is null, its value is intuitively 0.
5. Calculate the total column sum: val1 + val2 + carry.
6. Update the new carry for the next column: sum // 10.
7. Create a new Node with the actual digit for this column: sum % 10.
8. Advance the pointers elegantly!

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        curr = dummy
        carry = 0
        
        while l1 or l2 or carry:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            
            # Grade school addition
            total = val1 + val2 + carry
            carry = total // 10
            
            # Create node with digit
            curr.next = ListNode(total % 10)
            
            # Advance safely
            curr = curr.next
            if l1: l1 = l1.next
            if l2: l2 = l2.next
            
        return dummy.next

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (2)