如何将链表指定位置插入节点的迭代实现改写为递归版本？

实现思路 #

递归的核心是把遍历查找前驱节点的过程拆分为子问题：

• 当要在第index位插入节点时，如果index=0直接替换头节点，和原有逻辑一致
• 如果index>0，需要找到索引为index-1的前驱节点，每次递归将当前节点向后移动一位，同时目标位置减1，直到目标位置为1时，当前节点就是要找的前驱节点，直接执行插入操作即可

完整修改后的LinkedList类代码 #

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

    def get_head(self):
        return self._head

    def set_head(self, value):
        self._head = value

    # 递归辅助函数：从current节点开始，在对应pos位置的前一位插入新节点
    def _insert_recursive(self, current, pos, value):
        # 递归终止条件：pos=1时current就是前驱节点
        if pos == 1:
            current._next = Node(value, current.get_next())
            return
        # 否则递归处理下一个节点，位置减1
        self._insert_recursive(current.get_next(), pos - 1, value)

    def insert(self, value, index):
        if index == 0:
            self._head = Node(value, self._head)
            return
        # 索引大于0的情况调用递归辅助函数
        self._insert_recursive(self._head, index, value)

补充说明 #

如果需要加索引合法性校验，可以在insert入口处先判断索引是否超过链表长度，避免递归时出现空节点报错，上述实现和原有迭代逻辑保持了一致的行为。

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