LeetCode Solutions Blog

Add Two Numbers

Number: 2

Difficulty: Medium

Paid? No

Problem Description

Given two non-empty linked lists representing two non-negative integers where the digits are stored in reverse order, calculate their sum and return it as a linked list. Each node in the list contains a single digit. The two numbers do not have any leading zeros (except the number 0).

Key Insights

The digits are stored in reverse order, meaning the first node is the least significant digit.
A carry may need to propagate through subsequent nodes.
The two linked lists might be of different lengths.
Continue processing until both lists are fully traversed and any remaining carry is handled.

Space and Time Complexity

Time Complexity: O(max(n, m)), where n and m are the lengths of the two linked lists. Space Complexity: O(max(n, m) + 1) for the result list in the worst case.

Solution

The solution iterates through both linked lists node by node. For each pair of corresponding nodes, their values and any carry from the previous operation are summed. The result is decomposed into a current digit (modulo 10) and an updated carry (total divided by 10). A new node is created for the current digit and appended to the resulting linked list. This process continues until all nodes are processed and any leftover carry is added as a final node.

Code Solutions

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

def addTwoNumbers(l1, l2):
    # Initialize a dummy head node to simplify the result list construction.
    dummy = ListNode()
    current = dummy
    carry = 0
    
    # Traverse through both linked lists until all nodes and any carry are processed.
    while l1 or l2 or carry:
        # Get the current values; if a node is missing, use 0.
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        
        # Calculate the sum of current digits and carry.
        total = val1 + val2 + carry
        carry = total // 10   # Update carry for next iteration.
        digit = total % 10    # Compute current digit.
        
        # Append the digit as a new node in the result list.
        current.next = ListNode(digit)
        current = current.next
        
        # Move to the next nodes if available.
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next
            
    # Return the head of the newly formed linked list.
    return dummy.next