445 Add Two Numbers II

题目

Add Two Numbers II

题解

本题可以通过反转链表的方式来将问题转换为更容易求解的Add Two Numbers问题，也可以借助递归或者栈结构来求解，不过这里将介绍另外的特殊解法：我们可以直接将两个链表从最高位开始按位相加（先不处理进位），并构造一个从最低位指向最高位的链表，然后再一边处理进位一边反转链表。

graph TB
    subgraph numbers
        千位1[9] --> 百位1[8] --> 十位1[7] --> 个位1[6]
        千位2[5] --> 百位2[4] --> 十位2[3] --> 个位2[2]
    end
    subgraph sum
        direction RL
        个位和[8] --> 十位和[10] --> 百位和[12] --> 千位和[14]
    end
    subgraph result
        万位[1] --> 千位[5] --> 百位[3] --> 十位[0] --> 个位[8]
    end
    numbers -- 直接相加 --> sum -- 处理进位并反转 --> result

代码

class Solution:
    def countNodes(self, head: Optional[ListNode]):
        node = head
        count = 0
        while node is not None:
            count += 1
            node = node.next
        return count

    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        size1 = self.countNodes(l1)
        size2 = self.countNodes(l2)
        if size2 > size1:
            l1, l2 = l2, l1
            size1, size2 = size2, size1
        for _ in range(size1 - size2):
            l2 = ListNode(0, l2)

        node1 = l1
        node2 = l2
        head_node = None
        while node1 is not None and node2 is not None:
            sum = node1.val + node2.val
            if head_node is None:
                head_node = ListNode(sum)
            else:
                head_node = ListNode(sum, head_node)
            node1 = node1.next
            node2 = node2.next

        previous_node = None
        digit_node = head_node
        carry = 0
        while digit_node is not None:
            sum = digit_node.val + carry
            if sum >= 10:
                carry = 1
            else:
                carry = 0
            digit_node.val = sum % 10

            next_node = digit_node.next
            digit_node.next = previous_node
            previous_node = digit_node
            digit_node = next_node

        result_node = previous_node
        if carry > 0:
            result_node = ListNode(1, previous_node)
        return result_node