题解 | 链表相加(二)

# 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
        arr1=[]
        cur1=head1
        arr2=[]
        cur2=head2
        while cur1:
            arr1.append(cur1.val)
            cur1=cur1.next
        while cur2:
          arr2.append(cur2.val)
          cur2=cur2.next
        arr1=arr1[::-1]
        arr2=arr2[::-1]
        #print(arr1,arr2)
        p =0 
        len1=len(arr1)
        len2=len(arr2)
        i =0 
        j=0 
        res=[]
        while i<len1 or j<len2:
            #print(res)
            if i<len1 and j<len2:
                temp=arr1[i] +arr2[j]+p 
                res.append(temp%10)
                p= temp//10
                i+=1
                j+=1
            elif i>=len1 and j<len2:
                temp=arr2[j]+p
                res.append(temp%10)
                p=temp//10
                j+=1
            elif i<len1 and j>=len2:
                temp=arr1[i]+p
                res.append(temp%10)
                p=temp//10
                i+=1
        if p>0:
            res.append(p)
        # 反转
        res=res[::-1]
        newhead=ListNode(0)
        cur =newhead
        for i in range(len(res)):
            cur.next=ListNode(res[i])
            cur=cur.next
        return newhead.next
              
    """
    解题思路：
    [9,3,7],[6,3] 
     0.定义链表反转
     1. 将两个链表反转 [7,3,9]  [3,6], 定义结果链表 res=ListNode(-1) 
     2. p1 指向第一个链表 ，p2 指向第二个链表 p 表示进位
     3 .外侧循环条件 p1 或者p2 不为空 
        情况1； p1 and p2 都不为空 p1.val +p2.val +p 
        情况2： p1不为空 ，p2 为空 p1.val+p 
        情况3： p1为空，p2不为空 p2.val+p 
	 4. 如果循环结束之后p 还有进位作为节点值加入res
     5.  res.next 传入reverselist(res.next) 反转 返回newres
	 6. 返回newres 头结点
     时间复杂度： O(max(m,n))  
	 空间复杂度 O(1)  定义头结点变量
    """
    def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
        # write code here
        def reverselist(head:ListNode)->ListNode:
            if not head or not head.next:
                return head 
            cur =head
            pre=None
            while cur:
                next=cur.next
                cur.next=pre  
                pre =cur 
                cur=next
            return pre 
        # 判断
        if not head1 and not head2:
            return head1 
        if head1 and  not head2:
            return head1
        if not head1 and    head2:
            return head2
        
        res=ListNode(-1)
        cur =res 
        newhead1=reverselist(head1)
        #print(newhead1.val)
        newhead2=reverselist(head2)
        #print(newhead2.val)
        cur1=newhead1
        cur2=newhead2
        p=0 # 进位
        while cur1 or cur2:
            if cur1 and cur2:
                #print(cur1.val,cur2.val)
                temp =cur1.val+cur2.val+p 
                cur.next=ListNode(temp%10)
                p=temp//10
                cur=cur.next 
                cur1=cur1.next 
                cur2=cur2.next
            elif not cur1 and cur2:
                temp=cur2.val+p
                cur.next=ListNode(temp%10)
                p=temp//10
                cur=cur.next
                cur2=cur2.next
            elif cur1 and not cur2:
                temp=cur1.val+p
                cur.next=ListNode(temp%10)
                p=temp//10
                cur=cur.next
                cur1=cur1.next
        # 最后如果p 不为空 
        if p:
            cur.next=ListNode(p)
        #反转res 
        newres =reverselist(res.next)
        return newres