如何在链表插入方法中传入Node实例作为prev_node参数？

我实现了一个在链表指定节点后插入元素的方法：

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

class LinkedList:
    def __init__(self):
        self.head = None

    # 在链表头部插入节点
    def push_node(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    # 在指定节点后插入新节点
    def insert_node_after(self, data, prev_node):
        if self.head is None: 
            self.push_node(data)  # 原代码此处缺失右括号，已修正
        # if prev_node is None: self.push_node(data)
        new_node = Node(data)
        new_node.next = prev_node.next
        prev_node.next = new_node

    # 打印链表
    def print_list(self):
        current_node = self.head
        while current_node is not None:
            print(f'{current_node.data} -> ', end='')
            current_node = current_node.next
        print(f'None')

编写驱动代码运行时报错：

llist = LinkedList()
llist.push_node(4)
llist.push_node(3)
llist.push_node(2)
llist.push_node(1)
llist.push_node(100)

llist.insert_node_after(5, 2)

错误信息：

new_node.next = prev_node.next
AttributeError: 'int' object has no attribute 'next'

问题原因 #

你传入的2是整数类型，而insert_node_after方法的prev_node参数要求是Node类的实例，整数没有next属性，因此触发报错。

解决方法 #

方法一：手动查找目标Node实例后传入

先遍历链表，找到存储数据为2的节点对象，再将该对象传入方法：

llist = LinkedList()
llist.push_node(4)
llist.push_node(3)
llist.push_node(2)
llist.push_node(1)
llist.push_node(100)

# 遍历找到data为2的节点
target_node = None
current = llist.head
while current:
    if current.data == 2:
        target_node = current
        break
    current = current.next

if target_node:
    llist.insert_node_after(5, target_node)
    llist.print_list()
else:
    print("未找到指定的前驱节点")

方法二：修改insert_node_after方法，支持传入数据自动查找节点

直接修改方法，让它接受前驱节点的数据值，内部自动完成节点查找，调用时更便捷：

class LinkedList:
    # 其他方法保持不变，仅修改insert_node_after
    def insert_node_after(self, data, prev_data):
        if self.head is None:
            self.push_node(data)
            return
        
        # 查找对应数据的前驱节点
        current = self.head
        prev_node = None
        while current:
            if current.data == prev_data:
                prev_node = current
                break
            current = current.next
        
        if not prev_node:
            print("指定的前驱节点不存在")
            return
        
        new_node = Node(data)
        new_node.next = prev_node.next
        prev_node.next = new_node

修改后直接按原方式调用即可：

llist.insert_node_after(5, 2)
llist.print_list()

内容的提问来源于stack exchange，提问作者Future Billionaire