Python程序：添加两个链表中对应元素的位置

更多Python相关文章，请阅读：Python 教程

问题描述

给定两个非空链表表示两个非负整数，它们各自的位数是按照逆序方式存储的，并且它们的每个节点只存储单个数字。将这两数相加起来，则会返回一个新的链表来表示它们的和。

例如，假设链表1为 2 -> 4 -> 3 ，链表2为 5 -> 6 -> 4 ，那么链表1 + 链表2 = 7 -> 0 -> 8。

解法

首先，我们需要定义一个表示链表节点的类Node：

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

接下来，我们需要实现一个函数addTwoNumbers，该函数接收两个链表的头结点l1和l2作为参数，返回一个新的链表的头结点。具体实现过程如下：

def addTwoNumbers(l1: Node, l2: Node) -> Node:
    # 创建一个新链表的头结点
    dummy = Node(0)
    # 定义指针节点
    p, q, curr = l1, l2, dummy
    # 定义初始化的进位符
    carry = 0
    # 遍历链表l1和l2
    while p or q:
        # 如果l1链表还有节点，则获取节点值，否则置为0
        x = p.val if p else 0
        # 如果l2链表还有节点，则获取节点值，否则置为0
        y = q.val if q else 0
        # 计算相加结果，注意加上上一次的进位符
        total = x + y + carry
        # 计算新的进位符
        carry = total // 10
        # 计算当前节点的值
        curr.next = Node(total % 10)
        # 移动当前节点
        curr = curr.next
        # 如果链表l1还有节点，则移动指针p
        if p:
            p = p.next
        # 如果链表l2还有节点，则移动指针q
        if q:
            q = q.next
    # 这里需要注意最后一次计算可能会产生进位符，需要将其添加到新链表的末尾
    if carry > 0:
        curr.next = Node(carry)
    # 返回新链表的头结点
    return dummy.next

完整代码

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def addTwoNumbers(l1: Node, l2: Node) -> Node:
    dummy = Node(0)
    p, q, curr = l1, l2, dummy
    carry = 0
    while p or q:
        x = p.val if p else 0
        y = q.val if q else 0
        total = x + y + carry
        carry = total // 10
        curr.next = Node(total % 10)
        curr = curr.next
        if p:
            p = p.next
        if q:
            q = q.next
    if carry > 0:
        curr.next = Node(carry)
    return dummy.next


if __name__ == '__main__':
    l1 = Node(2, Node(4, Node(3)))
    l2 = Node(5, Node(6, Node(4)))
    result = addTwoNumbers(l1, l2)
    while result:
        print(result.val, end='')
        result = result.next

输出结果为：