如何正确构建并遍历 Python 中的单链表-Python教程-PHP中文网

如何正确构建并遍历 Python 中的单链表

本文详解链表构建常见陷阱：直接用 ListNode(l1[index+1]) 创建临时节点会导致链断裂，正确做法是先创建所有节点再逐个链接 next_node 指针。

本文详解链表构建常见陷阱：直接用 `listnode(l1[index+1])` 创建临时节点会导致链断裂，正确做法是先创建所有节点再逐个链接 `next_node` 指针。

在 Python 中实现单链表时，一个典型误区是在构建过程中错误地复用或提前实例化后续节点，从而破坏链式结构的连续性。您提供的代码中，list_node_builder 方法在构建 l1_list_nodes 时使用了如下逻辑：

new_node = ListNode(num, ListNode(l1[index+1]))

这行代码的问题在于：每次创建新节点时，都新建了一个独立、未被保存引用的临时 ListNode 作为 next_node。例如，当处理 'a' 时，ListNode('a', ListNode('b')) 创建了一个指向新 'b' 节点的指针；但当处理 'b' 时，又创建了另一个全新的 'b' 节点（ListNode('b', ListNode('c'))），而此前 'a' 所指向的 'b' 节点已丢失引用，成为孤立对象。最终导致链表仅保留头节点 'a' → 'b'（临时），而 'b' 的 next_node 实际指向的是另一个临时 'c'，但该 'b' 并非后续链中真实存在的节点——因此遍历时在第二个节点就中断。

✅ 正确构建方式应分两步：

统一创建所有节点，存入列表；
按序建立 next_node 引用，确保每个节点真正连接到下一个已保存的节点。

修正后的构建逻辑如下：

python-parallelization

将顺序 Python 代码转换为并行/并发实现，用于在需要并行化 Python 代码、提升性能时使用。

下载

def list_node_builder(self, l1: list[str], l2: list[int]) -> list[int]:
    print("***** Start building Linked List ******")

    # Step 1: 创建所有节点（不设 next_node）
    l1_nodes = [ListNode(val) for val in l1]
    l2_nodes = [ListNode(val) for val in l2]

    # Step 2: 顺序链接 next_node（跳过最后一个节点）
    for i in range(len(l1_nodes) - 1):
        l1_nodes[i].next_node = l1_nodes[i + 1]
    for i in range(len(l2_nodes) - 1):
        l2_nodes[i].next_node = l2_nodes[i + 1]

    print("***** Done building Linked List ******")
    return self.addTwoNumbers(l1_nodes[0], l2_nodes[0])

同时，建议优化遍历逻辑以提升健壮性与可读性：

def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> list:
    result_arr = []
    curr = l1
    print("***** Start traversing L1 only ******")
    while curr is not None:
        print(curr)
        result_arr.append(curr.val)  # 可选：收集值用于验证
        curr = curr.next_node
    print("***** End traversing L1 only ******")
    print(f"Traversed values: {result_arr}")
    return result_arr

⚠️ 注意事项：

ListNode.__dict__ = ("val", "next_node",) 是无效写法（__dict__ 是实例属性字典，不可赋值元组），应删除；
__str__ 中 self.next_node.value if self.next_node != None else -1 存在风险：若 next_node 非 None 但其 value 属性不可访问（如类型不支持），会抛异常；推荐改用 self.next_node.val if self.next_node else None；
链表构建务必保证引用唯一性：每个逻辑节点只能有一个存活引用，避免临时对象干扰链结构。

通过分离“节点创建”与“链接建立”两个阶段，可确保链表结构完整、遍历稳定，为后续如 addTwoNumbers 等双链表操作打下坚实基础。