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

用了两种方法求解：

1. 转化成数字在求解，先分别遍历两个链表得到两个链表的数字，然后数字求和，求和得到结果后把结果变成listnode就行了。时间复杂度是O(n)，空间复杂度是O(n)，但是没有通过，报错是时间超时，应该是python语言导致的，因此使用了第二种方法。

2. 把head1和head2两个链表的每个node分别放在两个list里面去，然后不断的pop，pop出来的是同一位的最低位数字，直接相加，若超过10，则记录jinwei=1，然后把链表1中的值改为pop出来的两个值%10。需要注意的是当比如list2 pop完了，那么我们只需要去pop list1就行了，然后加上jinwei，如果加上jinwei后小于10，就直接返回head1就行，如果jinwei一直大于10，需要前面加一个node，值为1.如果list1 pop完了，那么需要类似的去改list2里的值，但是此时同时还要改pop 出来的node的next指向，记得第一个pop出来的node要指向head1。

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head1 ListNode类 
# @param head2 ListNode类 
# @return ListNode类
#
class Solution:
    def addInList1(self , head1: ListNode, head2: ListNode) -> ListNode:
        # write code here
        #得到第一个数字
        num1 = ''
        cur = head1
        while cur:
            num1 += str(cur.val)
            cur = cur.next
        num2 = ''
        cur = head2
        while cur:
            num2 = num2+str(cur.val)
            cur = cur.next
        num1 = str(int(num1)+int(num2))
        head = ListNode(-1)
        cur = head
        for i in range(len(num1)):
            cur.next = ListNode(int(num1[i]))
            cur = cur.next
        return head.next

    def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
        list1 = []
        list2 = []
        cur = head1
        while cur:
            list1.append(cur)
            cur = cur.next
        cur = head2
        while cur:
            list2.append(cur)
            cur = cur.next
        jinwei = 0
        while len(list1) > 0 or len(list2) > 0:
            if len(list2) == 0:
                tmp1 = list1.pop()
                if tmp1.val + jinwei>=10:
                    tmp1.val = tmp1.val + jinwei - 10
                    jinwei = 1
                else:
                    tmp1.val = tmp1.val + jinwei
                    return head1
            elif len(list1) == 0:
                tmp2 = list2.pop()
                if tmp2.val + jinwei>=10:
                    tmp2.val = tmp2.val + jinwei - 10
                    jinwei = 1
                    tmp2.next = head1
                    head1 = tmp2
                else:
                    tmp2.next = head1
                    tmp2.val = tmp2.val + jinwei
                    return head2
            else:
                tmp1 = list1.pop() ; tmp2 = list2.pop()
                if tmp1.val + tmp2.val + jinwei >= 10:
                    tmp1.val = tmp1.val + tmp2.val + jinwei - 10
                    jinwei = 1
                else:
                    tmp1.val = tmp1.val + tmp2.val + jinwei
                    jinwei = 0
        if jinwei == 0:
            return head1
        else:
            head = ListNode(1)
            head.next = head1
            return head


head1 = ListNode(9)
head1.next = ListNode(3)
head1.next.next = ListNode(7)
head2 = ListNode(6)
head2.next = ListNode(3)
head = Solution().addInList(head2 , head1)
cur = head
while cur:
    print(cur.val)
    cur = cur.next