题解 | #BM11 链表相加(二)#

链表 + 分治法

1.先将两个链表倒置，再将倒置后的链表相加

2.相加时注意进位和处理循环

误区：

将两个链表转换为int，相加后再将int转换为链表，用这种方式无法通过所有的测试用例，因为链表的长度有可能会超过Int允许的最大长度而导致溢出而无法相加

class Solution:
    def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
        # write code here
        N1 = self.reverseListNode(head1)
        N2 = self.reverseListNode(head2)
        N0 = ListNode(-1)
        plus = 0
        while N1 or N2  or plus == 1:
            num1 = 0 if N1 is None else N1.val
            num2 = 0 if N2 is None else N2.val
            total = (num1 + num2 + plus) % 10 
            plus = int((num1 + num2 + plus) / 10)
            print(num1, num2, total, plus)
            N1 = N1.next if N1 else None
            N2 = N2.next if N2 else None
            temp = N0.next
            N0.next = ListNode(total)
            N0.next.next = temp
        return N0.next
           
    def reverseListNode(self, head: ListNode):
        pre_head = None
        while head:
            temp = head.next
            head.next = pre_head 
            pre_head = head
            head = temp
        return pre_head