HoRain云--【算法-链表-python】两数相加

云夏之末

1477人浏览 · 2025-09-25 09:30:00

云夏之末 · 2025-09-25 09:30:00 发布

🎬 HoRain云小助手：个人主页

🔥 个人专栏: 《Linux 系列教程》《c语言教程》

⛺️生活的理想，就是为了理想的生活!

⛳️ 推荐

前些天发现了一个超棒的服务器购买网站，性价比超高，大内存超划算！忍不住分享一下给大家。点击跳转到网站。

专栏介绍

专栏名称	专栏介绍
《C语言》	本专栏主要撰写C干货内容和编程技巧，让大家从底层了解C，把更多的知识由抽象到简单通俗易懂。
《网络协议》	本专栏主要是注重从底层来给大家一步步剖析网络协议的奥秘，一起解密网络协议在运行中协议的基本运行机制！
《docker容器精解篇》	全面深入解析 docker 容器，从基础到进阶，涵盖原理、操作、实践案例，助您精通 docker。
《linux系列》	本专栏主要撰写Linux干货内容，从基础到进阶，知识由抽象到简单通俗易懂，帮你从新手小白到扫地僧。
《python 系列》	本专栏着重撰写Python相关的干货内容与编程技巧，助力大家从底层去认识Python，将更多复杂的知识由抽象转化为简单易懂的内容。
《试题库》	本专栏主要是发布一些考试和练习题库（涵盖软考、HCIE、HRCE、CCNA等）

在 Python 中解决“两数相加”问题，关键点在于模拟加法运算过程，处理进位，以及遍历链表。题目通常会给出两个非空链表，表示两个非负整数。这些数字以逆序方式存储在链表中，每个节点存储一位数字。你需要将这两个数相加，并返回一个同样以逆序形式存储和的链表。

方法	时间复杂度	空间复杂度	核心思路
迭代法	O(max(m,n))	O(1)	同时遍历两链表，逐位相加处理进位，处理不等长情况。
递归法	O(max(m,n))	O(max(m,n))	递归逐位相加，递归栈隐式处理进位和节点创建。

下面是这两种方法的代码实现和解释。

📝 方法一：迭代法（推荐）

迭代法是解决这个问题最直观和高效的方法之一。其核心思想是同时遍历两个链表，逐位相加并处理进位。如果链表长度不同，则认为较短链表的后续位为0。最后如果进位不为0，则需要在新链表末尾添加一个节点。

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    dummy_head = ListNode(0)  # 创建一个哑节点作为结果链表的头节点前驱
    current = dummy_head      # 当前节点指针，用于构建新链表
    carry = 0                 # 进位值，初始为0

    # 遍历两个链表，直到所有节点处理完毕且无进位
    while l1 or l2 or carry:
        # 获取当前节点的值，如果链表已结束则视为0
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        
        # 计算当前位的和以及新的进位
        total = val1 + val2 + carry
        carry = total // 10   # 计算进位
        digit = total % 10    # 计算当前位的值
        
        # 创建新节点并将其连接到结果链表
        current.next = ListNode(digit)
        current = current.next  # 移动当前指针
        
        # 移动l1和l2的指针（如果存在下一个节点）
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next
            
    return dummy_head.next  # 返回结果链表的真正头节点

代码分析：

初始化：创建一个dummy_head（哑节点）简化链表头部的处理，current指针用于构建新链表，carry记录进位。
循环条件：while l1 or l2 or carry确保即使两个链表都遍历完，如果还有进位，循环也会继续。
值获取与计算：当前位相加时，若一个链表已结束，其值视为0。计算总和、新进位和当前位应存储的值。
构建新节点：根据计算出的当前位值创建新节点，并链接到current.next，然后移动current指针。
移动输入链表指针：如果l1或l2不为None，则移动到下一个节点。
返回结果：返回dummy_head.next，即结果链表的真正头节点。

📝 方法二：递归法

递归法通过函数调用栈隐式地处理位的相加和进位，代码更为简洁，但空间复杂度因递归调用栈而更高。

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbersRecursive(l1: ListNode, l2: ListNode, carry=0) -> ListNode:
    # 递归终止条件：两个链表都为空且无进位
    if not l1 and not l2 and carry == 0:
        return None

    # 计算当前位的值和进位
    val1 = l1.val if l1 else 0
    val2 = l2.val if l2 else 0
    total = val1 + val2 + carry
    new_carry = total // 10
    digit = total % 10

    # 创建当前节点
    current_node = ListNode(digit)

    # 准备下一个要处理的节点
    next1 = l1.next if l1 else None
    next2 = l2.next if l2 else None

    # 递归计算下一个节点，并连接到当前节点
    current_node.next = addTwoNumbersRecursive(next1, next2, new_carry)

    return current_node

代码分析：

终止条件：当两个链表都为None且进位为0时，返回None，结束递归。
当前位计算：与迭代法类似，计算当前位的总和、新进位和应存储的值。
创建节点：根据当前位的值创建新节点。
递归调用：获取两个链表的下一个节点（如果存在），递归计算后续节点的和，并将其作为当前节点的next。
返回当前节点：返回已连接好后续节点的当前节点。

调用递归函数：

# 假设 l1 和 l2 是定义好的链表
result = addTwoNumbersRecursive(l1, l2, 0)

💡 总结与建议

迭代法通常是更优的选择，因为它具有更低的空间复杂度（O(1)），尤其在处理很长链表时不会导致栈溢出。
递归法代码更简洁，但空间复杂度为O(max(m, n))，因为递归深度取决于较长链表的长度。它帮助理解递归操作链表的思想。
注意点：
- 务必处理进位，特别是在最高位相加后可能产生新进位。
- 使用哑节点（dummy head） 可以简化链表头节点的处理。
- 注意链表可能长度不同，在遍历时需判断节点是否为空。