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

题目：链表相加，并链表输出结果

思路；链表末尾对齐（长链表先走lenA-lenB步），确定较长链表，逐位相加存放数组中（按顺序各位次求和，正序存放）

为确定进位，先将数组逆序，逐步计算进位carry和当前数字，存放新List中

• 细节：初始carry=0，当前位的carry为val，计算下位carry = （number + val）/ 10, 余数 = （number + val）% 10

List从末尾逐位pop，建立新链表

python函数：

reversed(List)

数组索引不能是变量，插入新值用append()

# 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
        # 保存各位数字
        nums = []

        # 链表对齐
        len1 = 0
        len2 = 0
        head = head1
        while head:
            len1 += 1
            head = head.next
        head = head2
        while head:
            len2 += 1
            head = head.next
        
        # 确定较长链表
        if len1 > len2:
            curBig = head1
            curShort = head2
        else:
            curBig = head2
            curShort = head1

        # 对齐头链表，并将更长部分计入数组
        for i in range(0, abs(len1-len2)):
            nums.append(curBig.val)
            curBig = curBig.next
        
        # 同步移动,同位相加
        while curBig:
            nums.append(curBig.val + curShort.val)
            curBig = curBig.next
            curShort = curShort.next
        # 从数字生成数组，注意逆序生成
        nums = list(reversed(nums))

        carry = 0
        carrynums = []
        for i in range(0, len(nums)):
            val = carry
            carry = (nums[i] + val) // 10 # 每次能计算进位0 或 1
            number = (nums[i]+ val) % 10
            carrynums.append(number)
        
        if carry == 1 :
            carrynums.append(1)
        
        #出栈生成链表
        head = ListNode(0)
        p = head
        while len(carrynums) != 0:
            q = ListNode(carrynums.pop())
            p.next = q
            p = q
        return head.next