Python3实现两数相加：链表算法详解与代码优化

Dylan

发布时间：2026-10-14| 4人浏览过

原创

本文详细解析Python3中两个非空链表表示的非负整数相加问题。通过逆序存储特性，逐步演示如何创建新链表、处理进位及边界情况。文章对比了基础实现与优化后的代码逻辑，重点解决链表长度不一致及末尾进位问题，提供完整可运行的ListNode定义与Solution类实现，帮助开发者掌握链表遍历与节点操作技巧。

两数相加

给定两个非空链表，分别代表两个非负整数。数字以逆序方式存储，每个节点仅保存一位数字。要求计算这两个数的和，并以相同逆序链表形式返回结果。除数字0外，假设这两个数均不以0开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807。

示例 2：

输入：l1 = [0], l2 = [0] 输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]

思路：

1. 初始化一个新链表的头节点，其值为l1和l2首节点之和。 2. 同时遍历两个链表，只要任一链表未遍历完毕，则继续循环。 3. 在每次迭代中，生成当前节点cur的下一个节点，其值等于两链表对应节点值之和加上当前节点产生的进位。 4. 更新当前节点cur的值为模10的结果（即保留个位），并处理进位。 5. 循环结束后，若最高位产生进位（即cur.val >= 10），需新增一个节点存储进位值。 6. 返回头节点。

根据题目注释，ListNode类用于构建链表，默认next为None，val为0。 Definition for singly-linked list. class ListNode: def init(self, val=0, next=None): self.val = val self.next = next


# 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:
  head = ListNode(l1.val+l2.val)
  current = head
  while l1.next or l2.next:
   l1 = l1.next if l1.next else ListNode()
   l2 = l2.next if l2.next!=None else ListNode()
   current.next = ListNode(l1.val+l2.val+current.val//10)
   current.val = current.val%10
   current = current.next
  if current.val >= 10:
   current.next = ListNode(current.val//10)
   current.val = current.val%10
  return head

初步改进尝试：虽然增加了空间复杂度，但原本设想当一方链表为None时直接连接另一方即可。然而实际测试发现逻辑存在漏洞，导致错误。

因此补充了while循环以处理剩余节点。


> [9999]

# 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:
  head = ListNode(l1.val+l2.val)
  current = head
  while l1.next and l2.next:
   l1 = l1.next 
   l2 = l2.next 
   current.next = ListNode(l1.val+l2.val+current.val//10)
   current.val = current.val%10
   current = current.next
  if l1.next == None and l2.next :
   while l2.next:
    l2 = l2.next
    current.next= ListNode(l2.val+current.val//10)
    current.val = current.val%10
    current = current.next
    current.next = l2.next
  elif l2.next == None and l1.next:
   while l1.next:
    l1 = l1.next
    current.next= ListNode(l1.val+current.val//10)
    current.val = current.val%10
    current = current.next
    current.next = l2.next
  if current.val >= 10:
   current.next = ListNode(current.val//10)
   current.val = current.val%10
  return head