2. Add Two Numbers (Medium)

Pyodide

Editor (session: default) Run

# Type here

Output Clear

Run

Editor (session: default) Run

# 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, l2):
        dummy_head = ListNode(0)
        current = dummy_head
        carry = 0

        while l1 or l2 or carry:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            total_sum = val1 + val2 + carry
            carry = total_sum // 10
            new_digit = total_sum % 10

            current.next = ListNode(new_digit)
            current = current.next

            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy_head.next

# Helper function to convert a list of digits to a linked list (in reverse order)
def create_linked_list(digits):
    dummy_head = ListNode(0)
    current = dummy_head
    for digit in digits:
        current.next = ListNode(digit)
        current = current.next
    return dummy_head.next

# Helper function to convert a linked list to a list of digits
def linked_list_to_list(node):
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result


# Example 1: (2 -> 4 -> 3) + (5 -> 6 -> 4) -> (7 -> 0 -> 8)
l1_ex1 = create_linked_list([2, 4, 3])
l2_ex1 = create_linked_list([5, 6, 4])
print(linked_list_to_list(Solution().addTwoNumbers(l1_ex1, l2_ex1)), "\n")

# Example 2: (0) + (0) -> (0)
l1_ex2 = create_linked_list([0])
l2_ex2 = create_linked_list([0])
print(linked_list_to_list(Solution().addTwoNumbers(l1_ex2, l2_ex2)), "\n")

# Example 3: (9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9) + (9 -> 9 -> 9 -> 9) -> (8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 1)
l1_ex3 = create_linked_list([9, 9, 9, 9, 9, 9, 9])
l2_ex3 = create_linked_list([9, 9, 9, 9])
print(linked_list_to_list(Solution().addTwoNumbers(l1_ex3, l2_ex3)))

Output Clear

Solution

class Solution:
    def addTwoNumbers(self, l1, l2):
        dummy_head = ListNode(0)
        current = dummy_head
        carry = 0

        while l1 or l2 or carry:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            total_sum = val1 + val2 + carry
            carry = total_sum // 10
            new_digit = total_sum % 10

            current.next = ListNode(new_digit)
            current = current.next

            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy_head.next

Function Description

Source code in python/_2.py

class Solution:
    def addTwoNumbers(self, l1, l2):
        dummy_head = ListNode(0)
        current = dummy_head
        carry = 0

        while l1 or l2 or carry:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            total_sum = val1 + val2 + carry
            carry = total_sum // 10
            new_digit = total_sum % 10

            current.next = ListNode(new_digit)
            current = current.next

            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy_head.next

addTwoNumbers(l1, l2)

Source code in python/_2.py

def addTwoNumbers(self, l1, l2):
    dummy_head = ListNode(0)
    current = dummy_head
    carry = 0

    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        total_sum = val1 + val2 + carry
        carry = total_sum // 10
        new_digit = total_sum % 10

        current.next = ListNode(new_digit)
        current = current.next

        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None

    return dummy_head.next

Explanation

The "Add Two Numbers" problem is a classic data structures challenge that requires adding two non-negative integers represented as linked lists. Crucially, the digits are stored in reverse order, with each node containing only a single digit. For instance, the number 342 would be represented as a list \(2 \to 4 \to 3\). The objective is to return a new linked list that represents the sum of the two input numbers. This problem assesses a developer's proficiency in handling pointer manipulation and basic arithmetic while traversing linked structures.

The solution involves traversing both linked lists simultaneously, starting from the head (the least significant digit). A dummy head node is typically initialized to simplify the creation and return of the new resulting list. A key component of the solution is tracking the carry-over value from one digit position to the next. In each step of the traversal, the algorithm sums the current digits from both lists (if they exist) along with the current carry-over. The new digit for the resulting list is the remainder of this sum when divided by 10, and the new carry-over is the quotient (sum divided by 10).

The traversal continues as long as there are still digits left in either of the input lists, or if the carry-over value is greater than zero. This ensures that even if one list is shorter than the other, or if a final carry-over remains (e.g., adding \(99 + 1\) results in \(100\)), the resulting list is correctly extended. This approach effectively mimics manual addition, resulting in a single pass solution with a time complexity of \(O(\max(m, n))\), where \(m\) and \(n\) are the lengths of the two input linked lists, making it an efficient and industry-standard solution.