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

# 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:
        if head1 == None:
            return head2
        if head2 == None:
            return head1

        def reverse(head):
            pre, cur, nex = None, head, head

            count = 0
            while nex != None:
                nex = nex.next
                cur.next = pre
                pre = cur
                cur = nex
                count += 1
            return count, pre

        n, head1 = reverse(head1)
        m, head2 = reverse(head2)

        if n < m:
            head1, head2 = head2, head1
            n, m = m, n        

        ans = head1
        if n == m:
            for _ in range(m - 1):
                temp = head1.val + head2.val
                head1.val = temp % 10
                head1.next.val += temp // 10

                head1 = head1.next
                head2 = head2.next
            temp = head1.val + head2.val
            if temp < 10:
                head1.val = temp
            else:
                head1.val = temp % 10
                newNode = ListNode(temp // 10)
                head1.next = newNode
                head1 = head1.next     
        else:
            for _ in range(m):
                temp = head1.val + head2.val
                head1.val = temp % 10
                head1.next.val += temp // 10

                head1 = head1.next
                head2 = head2.next
            for i in range(n-m-1):
                if head1.val < 10:
                    break
                else:
                    head1.val = head1.val % 10
                    head1.next.val += 1
                    head1 = head1.next
            if head1.val >= 10:
                newNode = ListNode(head1.val // 10)
                head1.val = head1.val % 10
                head1.next = newNode
                head1 = head1.next
        _, ans = reverse(ans)
        
        return ans