To solve this problem, we need to add two numbers represented as linked lists in reverse order. Each node in the linked list contains a single digit, and the digits are stored in reverse order (least significant digit first). The goal is to return the sum as a new linked list in the same reversed format.

Approach

1. Reverse Order Handling: Since the linked lists are in reverse order, we can directly start adding digits from the head of each list (which corresponds to the least significant digit).
2. Carry Management: When adding digits, we need to keep track of any carry that results from the sum of two digits (and the carry from the previous step). The carry is calculated as the integer division of the sum by 10, and the digit to store is the remainder of the sum divided by 10.
3. Unequal Length Lists: If one list is longer than the other, we treat the missing digits of the shorter list as 0.
4. Final Carry: After processing all digits from both lists, if there is any remaining carry, we add it as a new node at the end of the result list.

Solution Code

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

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    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

        total = val1 + val2 + carry
        carry = total // 10
        current.next = ListNode(total % 10)

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

    return dummy.next

Explanation

1. Dummy Head: We use a dummy head to simplify the process of creating the result list. This avoids checking if the result list is empty when adding the first node.
2. Iteration: We iterate through both linked lists (and the carry) until all digits are processed and there is no remaining carry.
3. Digit Calculation: For each step, we compute the sum of the current digits from both lists plus the carry. We then update the carry and create a new node with the resulting digit (sum mod 10).
4. Move Pointers: We move the pointers of the input lists (if they exist) and the result list to the next node.
5. Return Result: The result list starts from the next node of the dummy head (since the dummy head itself is a placeholder).

This approach efficiently handles all edge cases, including unequal-length lists and remaining carry, and runs in O(max(n, m)) time complexity, where n and m are the lengths of the two input lists. The space complexity is O(max(n, m)) for the result list.

作者声明:本文包含人工智能生成内容。