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

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head1 ListNode类 
# @param head2 ListNode类 
# @return ListNode类
#
class Solution:
    def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
        # write code here

        #翻转链表
        def ReverseLink(head):

            pre = ListNode(-1)
            pre.next = None

            while head:
                next = head.next
                head.next = pre.next
                pre.next = head
                head = next
            return pre

        head1 = ReverseLink(head1)
        head2 = ReverseLink(head2)


        #构造一个新的链表，获取要相加的俩个链表的第一个结点，并初始化累加器
        head3 = ListNode(-1)


        head1=head1.next
        head2=head2.next
        Acc=0


        #累加，当有进位时，将ACC设置为1，下次累加时，记得加上Acc的值，加完以后Acc重置为0
        while head1 and head2:
            
            s = head1.val + head2.val+Acc
            Acc=0
            head1=head1.next
            head2=head2.next


            #判断是否满足进位的条件
            if s>=10:
                s=s-10
                Acc=1

            else:
                pass


            #将累加的结果拼接到新的记录结果的L3中
            node=ListNode(s)
            node.next=head3.next
            head3.next=node
        

        #如果head1为真，说明L1的长度大于L2的长度，退出原因是L2为空导致的，需要将L1拼接到L3
        #,但是退出循环之前有可能Acc为1，因此要把上次的Acc累加进来
        while head1:
            
            s=head1.val+Acc

            head1=head1.next
            Acc=0
            if s>=10:
                s=s-10
                Acc=1
            node = ListNode(s)
            node.next=head3.next
            head3.next=node
        
        #head2的循环与Head1同理
        while head2:
            s=head2.val+Acc
            Acc=0
            head2=head2.next
            if s>=10:
                s=s-10
                Acc=1
            node = ListNode(s)
            node.next=head3.next
            head3.next=node

        #有可能head1或者head2与上次退出循环的acc又产生了进位，然后Head1或者head2退出了就，这时，需要再判断一次Acc的值
        if Acc==1:
            node = ListNode(1)
            node.next=head3.next
            head3.next=node

        #head3=ReverseLink(head3)
        return head3.next