题目描述

题解

加法运算直接求解

解法一：

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: # l1作为结果保留的链表 head = l1 while l1 and l2: Sum = l1.val + l2.val # 商，即进位 quo = Sum // 10 # 余数，保留在当前l1中 remainder = Sum % 10 l1.val = remainder # 如果存在进位，则对l1的下一位加上进位 if quo > 0: if l1.next: l1.next.val += quo else: l1.next = ListNode(quo) l2 = l2.next # 这样写的原因见下方知识点总结 .....(1) if l1.next: l1 = l1.next else: break # l1和l2长度不同时的情况分析 if not l1 and not l2: return head elif l1 and not l2: while l1: quo = l1.val // 10 if quo > 0: remainder = l1.val % 10 l1.val = remainder if l1.next: l1.next.val += quo else: l1.next = ListNode(quo) l1 = l1.next else: return head else: # 这里和上面的（1）是配合的 ....(2) l1.next = l2 return head

  运行结果如下。时间复杂度为$O(N+M)$，N，M分别是l1，l2的长度；空间复杂度为$O(1)$。

知识点总结：   1.常见运算符：%为取余，//为求商；   2.head是l1的浅复制，l1的变化直接导致了head链表的变化，但是当经过l1 = l1.next操作时，导致l1 == None时，此时如果对l1进行操作，如l1 = l2，不会引起head的变化，见下图。所以在上面处理时，不能让l1出现None，否则在最后的l1 = l2时，会出现“断链”的情况。如l1：0；l2：7，3；此时如果直接在（1）处l1 = l1.next，在（2）处l1 = l2，结果就只有7，而没有3，因为l1在退出while循环时为None，已经“断链”，后续的l1 = l2，不会最head产生操作了。

解法二：

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: # 创建一个结点值为 None 的头结点, dummy 和 p 指向头结点, dummy 用来最后返回, p 用来遍历 # 哑节点，.next作为结果 dummy = p = ListNode(None) s = 0 # 初始化进位 s 为 0 while l1 or l2 or s: # 如果 l1 或 l2 存在, 则取l1的值 + l2的值 + s(s初始为0, 如果下面有进位1, 下次加上) s += (l1.val if l1 else 0) + (l2.val if l2 else 0) p.next = ListNode(s % 10) # p.next 指向新链表, 用来创建一个新的链表 p = p.next # p 向后遍历 s //= 10 # 有进位情况则取模, eg. s = 18, 18 // 10 = 1 l1 = l1.next if l1 else None # 如果l1存在, 则向后遍历, 否则为 None l2 = l2.next if l2 else None # 如果l2存在, 则向后遍历, 否则为 None return dummy.next # 返回 dummy 的下一个节点, 因为 dummy 指向的是空的头结点, 下一个节点才是新建链表的后序节点

  运行结果如下。

转化为整数再还原回链表

class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: #1.还原两个非负整数； num1 = str(l1.val) while l1.next: l1 = l1.next num1 += str(l1.val) num1 = int(num1[::-1]) num2 = str(l2.val) while l2.next: l2 = l2.next num2 += str(l2.val) num2 = int(num2[::-1]) #2.求和； num = str(num1 + num2) #3.还原结果。 L = len(num) result = ListNode(int(num[0])) for i in range(1, L): result = ListNode(int(num[i]), result) return result

  运行结果如下。

递归

class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: def dfs(l, r, i): if not l and not r and not i: return None s = (l.val if l else 0) + (r.val if r else 0) + i node = ListNode(s % 10) node.next = dfs(l.next if l else None, r.next if r else None, s // 10) return node return dfs(l1, l2, 0)

  运行结果如下。

知识点总结：   递归的使用：     1.何时使用递归     2.递归的典型用例：阶乘，斐波那契数列，快速排序，汉诺塔等   在本题中，两个链表的加法操作，就是重复对每一位进行加法运算，所以递归适合处理重复工作的情况，以每一位以及进位位作为递归函数的参数。