Python单链表insert方法死循环及头插入失败问题排查求助

问题原因 #

1. 头插失效：当index=0时，虽然创建了新节点并让它的next指向原头节点，但没有将链表的self.head更新为这个新节点，原头节点依然是链表的起始节点，导致头插操作完全没生效。
2. 死循环问题：在非头插的分支中，代码执行temp = locate后，将aux.next = temp，同时locate.next = aux，这就形成了locate -> aux -> locate的循环链表结构。遍历链表时会在这两个节点之间无限循环，无法终止。

修复后的代码 #

首先确保insert是链表类（比如LinkedList）的成员方法，修复后的完整代码示例：

class Node:
    '''辅助链表的节点类'''
    def __init__(self, content):
        self.data = content  # 把属性名从node改成data，语义更清晰
        self.next = None

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

    def insert(self, content, index: int = 0) -> bool:
        '''在指定索引位置插入数据'''
        new_node = Node(content)
        # 处理头插情况
        if index == 0:
            new_node.next = self.head
            self.head = new_node  # 关键：更新链表头节点
            return True
        
        # 处理非头插情况
        current = self.head
        # 遍历到目标位置的前一个节点
        for _ in range(index - 1):
            if current is None:
                raise IndexError("Index out of range!")
            current = current.next
        
        # 保存原current的后继节点，避免断链和循环
        next_node = current.next
        current.next = new_node
        new_node.next = next_node
        return True

    # 可选：添加遍历方法用于测试
    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

修复说明 #

• 头插时新增self.head = new_node，确保链表头指向新插入的节点。
• 非头插时，先保存当前节点的后继节点next_node，再将新节点插入到当前节点和后继节点之间，避免形成循环。
• 把Node类的self.node改成self.data，属性名更符合语义，便于理解。

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