本文共 5878 字，大约阅读时间需要 19 分钟。

目录

题目描述

给出两个非空的（单向）链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示他们的和。您可以假设除数字0以外，这两个数都不会以0开头。

输入/输出示例

解决方案

因为两个链表是单向链表，且是从个位数开始至最高位存储的每一个数字，因此依次对两个链表的每一位做加法即可。

在做加法的时候需要注意一点，如果两个数相加超过了9，必须向更高位进位，即高位+1。如果高位+1后继续大于9，重复进位，直至小于10。

需要考虑的一点是，两个数长度不相等的情况。如果number1长度大于number2，则只需要考虑number1后面节点所保存的数字有没有大于9的，有则进位；如果number2的长度大于number1，则只需要将number1的尾指针指向number2后续的节点即可。

解决方案大概有两种

第一种：在原有链表上做加减

第二种：创建新的链表保存结果

代码

方案一：在原有链表上做加减

这种方案是最节省空间消耗的。即在原链表的基础上保存相加后的结果，最小限度的开辟新节点。需要注意的是该方法会破坏一个链表的原有数据。

# Definition for singly-linked list.class ListNode:    def __init__(self, x):        self.val = x        self.next = Noneclass Solution:    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:        head = l1        while True:            add = l1.val + l2.val            if add >= 10:                l1.val = add - 10                if l1.next is None:                    node = ListNode(1)                    l1.next = node                else:                    l1.next.val += 1            else:                l1.val = add            if l1.next is not None and l2.next is None:                while l1.next is not None:                    l1 = l1.next                    if l1.val >= 10:                        l1.val = l1.val - 10                        if l1.next is None:                            node = ListNode(1)                            l1.next = node                            break                        else:                            l1.next.val += 1                return head            if l1.next is None and l2.next is None:                return head            if l1.next is None:                l1.next = l2.next                return head            l1 = l1.next            l2 = l2.next

方案二：创建新的链表保存结果

开辟新的节点保存计算结果，这种方式代码逻辑更加清晰简单，也不会破坏原始的链表结构。缺点是增加了空间消耗。

# Definition for singly-linked list.class ListNode:    def __init__(self, x):        self.val = x        self.next = Noneclass Solution:    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:        head = ListNode(None)        pre = head        sum = 0        while l1 or l2 or sum:            sum += (l1.val if l1 else 0) + (l2.val if l2 else 0)            pre.next = ListNode(sum % 10)            pre = pre.next            sum //= 10            l1 = l1.next if l1 else None            l2 = l2.next if l2 else None        return head.next

代码走读

方案一

# Definition for singly-linked list.# LeetCode定义的单向链表节点class ListNode:    def __init__(self, x):        self.val = x        self.next = None# LeetCode定义的解决方法类class Solution:    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:        # head指向l1的头节点，最终要将head返回        head = l1        while True:            # 对应位相加。如果相加结果大于或等于10（说明需要进位），则向高位进位。这里不再对高位进位后是否在需要进位做检查            add = l1.val + l2.val            if add >= 10:                l1.val = add - 10                if l1.next is None:                    node = ListNode(1)                    l1.next = node                else:                    l1.next.val += 1            else:                l1.val = add            # 如果l2的长度小于l1，则检查l1和l1后续节点保存的数字，大于10则进位。最后返回头指针            if l1.next is not None and l2.next is None:                while l1.next is not None:                    l1 = l1.next                    if l1.val >= 10:                        l1.val = l1.val - 10                        if l1.next is None:                            node = ListNode(1)                            l1.next = node                            break                        else:                            l1.next.val += 1                return head            # 如果此时l1和l2都遍历完，返回头指针            if l1.next is None and l2.next is None:                return head                        # 如果l1的长度小于l2，则只需要将l1的尾指针指向l2后续的节点即可            if l1.next is None:                l1.next = l2.next                return head            # l1和l2的指针向下迭代            l1 = l1.next            l2 = l2.next# 自测用例if __name__ == '__main__':    num1 = 5    num2 = 5    head1 = ListNode(0)    pre = head1    for n in str(num1)[::-1]:        pre.next = ListNode(int(n))        pre = pre.next    l1 = head1.next    head2 = ListNode(0)    pre = head2    for n in str(num2)[::-1]:        pre.next = ListNode(int(n))        pre = pre.next    l2 = head2.next    s = Solution()    result = s.addTwoNumbers(l1, l2)    result_list = []    while result is not None:        result_list.append(result.val)        result = result.next    print(result_list[::-1])

方案二

# LeetCode定义链表节点类# Definition for singly-linked list.class ListNode:    def __init__(self, x):        self.val = x        self.next = None# LeetCode定义的解决方法类class Solution:    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:        # 定义新链表的表头和指针        head = ListNode(None)        pre = head          # 每一步求和的暂存变量        sum = 0        while l1 or l2 or sum:            # 计算求和结果，如果l1或l2为空，则视为0            sum += (l1.val if l1 else 0) + (l2.val if l2 else 0)            # 创建新的节点，将sum值的个位作为新节点的值            pre.next = ListNode(sum % 10)            # 移动指针            pre = pre.next            # 求sum值的十位数，并保留            sum //= 10            # l1和l2向下移动            l1 = l1.next if l1 else None            l2 = l2.next if l2 else None        return head.next# 自测用例if __name__ == '__main__':    num1 = 243    num2 = 564    head1 = ListNode(0)    pre = head1    for n in str(num1)[::-1]:        pre.next = ListNode(int(n))        pre = pre.next    l1 = head1.next    head2 = ListNode(0)    pre = head2    for n in str(num2)[::-1]:        pre.next = ListNode(int(n))        pre = pre.next    l2 = head2.next    s = Solution()    result = s.addTwoNumbers(l1, l2)    result_list = []    while result is not None:        result_list.append(result.val)        result = result.next    print(result_list[::-1])

传送门

转载地址：http://ldsoi.baihongyu.com/