两数相加

Leetcode Link: 2. 两数相加 - 力扣（LeetCode） (leetcode-cn.com)

题目

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

解法一

思路：每次新建一个节点，公共部分直接计算放进去，有一个为None直接把指针指到不是None的上面，但是要注意jinWei的值要多判断，多考虑，

题解：我的版本，时间复杂度$O(max(M,N))$, 空间复杂度$O(min(M,N))$

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        jinWei = 0
        newDummy = ListNode()
        cur = newDummy
        # 把重复部分相加
        while(l1!=None and l2!=None):
		        # 保留个位数
                val = (l1.val + l2.val + jinWei) % 10 
                # 计算进位，即计算十位数（这里不会）        
                jinWei =floor((l1.val + l2.val + jinWei - val) / 10)   
                newNode = ListNode(val)
                cur.next = newNode
                # 全部往下走, 这里经常把cur给忘了
                l1 = l1.next
                l2 = l2.next
                cur = cur.next
 
        # now 总是没有走完的那个
        # 全走完了是None也行，进不去下面的while
        now = l1 if l1!=None else l2
 
        while(now != None):
            if jinWei != 0:
                val = (now.val + jinWei) % 10
                jinWei = floor((now.val + jinWei - val) / 10)
                newNode = ListNode(val)
                cur.next = newNode
 
                now = now.next
                cur = cur.next
            else:
                cur.next = now
                break
        # 如果现在还有进位，则说明需要再加一个节点，比如 [5] + [5] = [0, 1]  
        if jinWei == 1:
            newNode = ListNode(1)
            cur.next = newNode
      
        return newDummy.next

上面每次都新建了一个，如果不新建的话，可以采用复用其中一个节点的方式，但是最好建立一个newDummy的头节点。然而这种方法会破坏其中一个链表。时间复杂度$O(max(M,N))$, 空间复杂度$O(1)$

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        jinWei = 0
        newDummy = ListNode()
        cur = newDummy
        # 把重复部分相加
        while(l1!=None and l2!=None):
                val = (l1.val + l2.val + jinWei) % 10         
                jinWei =floor((l1.val + l2.val + jinWei - val) / 10)
 
                l1.val = val
                cur.next = l1
                # 全部往下走, 这里经常把cur给忘了
                l1 = l1.next
                l2 = l2.next
                cur = cur.next
 
        # now 总是没有走完的那个
        # 全走完了是None也行，进不去下面的while
        now = l1 if l1!=None else l2
 
        while(now != None):
            if jinWei != 0:
                val = (now.val + jinWei) % 10
                jinWei = floor((now.val + jinWei - val) / 10)
                now.val = val
                cur.next = now
 
                now = now.next
                cur = cur.next
            else:
                cur.next = now
                break
        # 如果现在还有进位，则说明需要再加一个节点，比如 [5] + [5] = [0, 1]  
        if jinWei == 1:
            newNode = ListNode(1)
            cur.next = newNode
      
        return newDummy.next

启发和联系

本题中，最重要的是考虑题目中的示例3、4，jinWei的值要贯穿于整个算法中，时刻考虑该值，最后根据这个值来决定是不是需要添加新得尾节点。