Add Two Numbers - Python Solution

1. Introduction

"Add Two Numbers" is a classic problem in the realm of data structures, specifically linked lists. It involves adding two numbers represented by two linked lists, where each node contains a single digit of the number in reverse order. This problem is essential for understanding linked list manipulation and basic arithmetic operations in a data structure context.

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. The task is to add these two numbers and return the sum as a linked list. It is assumed that the two numbers do not contain any leading zeros, except the number 0 itself.

2. Solution Steps

1. Initialize a dummy node to help in building the result linked list.

2. Initialize variables to keep track of the carry and the current nodes in both lists.

3. Iterate through the lists while any of the lists has nodes left or there is a carry.

4. For each iteration, calculate the sum of the current digits and the carry.

5. Update the carry for the next iteration.

6. Create a new node with the digit value of the sum % 10 and attach it to the result list.

7. Move to the next nodes in the input lists, if available.

8. Return the next node of the dummy node, which is the start of the result linked list.

3. Code Program

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

    while l1 or l2 or carry:
        val1 = (l1.val if l1 else 0)
        val2 = (l2.val if l2 else 0)
        carry, out = divmod(val1 + val2 + carry, 10)

        current.next = ListNode(out)
        current = current.next

        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

    return dummy.next

# Example Usage
# Creating lists for demonstration: [2 -> 4 -> 3] and [5 -> 6 -> 4]
l1 = ListNode(2, ListNode(4, ListNode(3)))
l2 = ListNode(5, ListNode(6, ListNode(4)))
result = addTwoNumbers(l1, l2)
# Output the list
output = []
while result:
    output.append(result.val)
    result = result.next
print(output)

Output:

[7, 0, 8]

Explanation:

1. ListNode Class: A simple ListNode class is used to represent each node of the linked list.

2. Dummy Node: A dummy node is initialized to simplify the process of building the result list.

3. Iterative Addition: The two lists are iterated through, adding corresponding digits and considering the carry from the previous addition.

4. Carry Handling: The carry for each addition is calculated and used in the next iteration.

5. Building Result List: A new node is created for each digit of the result and linked to the current node.

6. List Traversal: The function traverses through the lists, handling cases where the lists are of different lengths.

7. Final Result: The result linked list represents the sum of the two input numbers, stored in reverse order.