Python 链表相加：算法详解与代码实现

本文将详细介绍如何使用 Python 语言实现两个链表相加，并提供完整的代码示例。假设你已经熟悉了链表的基本概念。

问题描述:

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

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

示例：

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

代码实现:

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:
        dummy = ListNode(0)
        current = dummy
        carry = 0
        
        while l1 or l2 or carry:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            carry, val = divmod(val1 + val2 + carry, 10)
            current.next = ListNode(val)
            current = current.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        
        return dummy.next

算法思路:

定义一个 dummy 节点和一个 current 节点，初始值都为 0。
定义一个变量 carry 表示进位，初始值为 0。
遍历两个链表，每次取出对应节点的值相加，再加上进位，计算出新的进位和当前位的值。
将当前位的值作为一个新节点插入到 current 节点的后面，然后将 current 指针指向这个新节点。
如果链表 l1 或 l2 还有剩余节点，则继续遍历。
最后返回 dummy 节点的 next 指针，即为相加后的链表。

代码解析:

dummy 节点用于简化操作，方便返回结果。
current 节点用于指向当前节点，方便插入新节点。
carry 变量用于记录进位，如果当前位相加的值大于等于 10，则进位为 1，否则为 0。
divmod(val1 + val2 + carry, 10) 用于计算新的进位和当前位的值，返回值分别为 carry 和 val。
ListNode(val) 创建一个新的节点，并将当前位的值 val 存储在节点中。
current.next = ListNode(val) 将新节点插入到 current 节点的后面。
current = current.next 将 current 指针指向新节点。
l1 = l1.next if l1 else None 用于遍历链表 l1，如果 l1 还有剩余节点，则将 l1 指针指向下一个节点，否则将 l1 指针设置为 None。
l2 = l2.next if l2 else None 用于遍历链表 l2，如果 l2 还有剩余节点，则将 l2 指针指向下一个节点，否则将 l2 指针设置为 None。
最后返回 dummy.next 指针，即为相加后的链表。

总结:

本文详细介绍了使用 Python 语言实现两个链表相加的算法，并提供了完整的代码示例。算法思路清晰易懂，适合初学者学习理解。希望本文对你有所帮助！