递归实现LinkedList指定位置插入方法遇问题求助

原代码核心问题分析 #

• 无限循环：无论是否找到插入位置，最后都会执行递归调用self.insert(...)，没有正确终止递归流程。
• 插入逻辑错误：
  • 当position == index时，直接修改self._head，忽略了插入位置不是头部的情况，且没有正确连接新节点与后续节点。
  • new_node参数的使用完全无效，没有起到连接链表的作用。
  • 尾部插入的条件判断逻辑混乱，导致无法正确处理超出链表长度的插入请求。

修正后的递归Insert实现 #

def insert(self, val, position, current=None, prev=None, index=0):
    # 空链表直接插入
    if self._head is None:
        self._head = Node(val)
        return
    
    # 初始化递归参数
    if current is None:
        current = self._head
    
    # 插入到头部（position=0）
    if position == 0:
        new_node = Node(val)
        new_node.next = self._head
        self._head = new_node
        return
    
    # 到达目标位置，插入到prev节点之后
    if position == index:
        new_node = Node(val)
        new_node.next = current
        prev.next = new_node
        return
    
    # 到达链表尾部，且position大于当前长度，插入到尾部
    if current.next is None and position > index:
        current.next = Node(val)
        return
    
    # 递归遍历下一个节点
    self.insert(val, position, current.next, current, index + 1)

修正逻辑说明 #

• 递归参数优化：新增prev参数记录当前节点的前一个节点，方便插入操作时修改指针。
• 终止条件明确：每种插入场景（头部、目标位置、尾部）处理完成后都直接return，避免无限递归。
• 指针连接正确：插入新节点时，先将新节点的next指向当前节点，再将前一个节点的next指向新节点，保证链表连续性。
• 边界情况处理：单独处理空链表、插入头部、插入尾部的场景，覆盖所有可能的插入位置。

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