如何在Java中为有序链表实现递归插入方法？

完整实现代码 #

// 对外暴露的单参数主方法
public void insert(E data) {
    head = insertRecursive(head, data);
}

// 私有递归辅助方法，内部处理节点递归逻辑
private Node<E> insertRecursive(Node<E> current, E data) {
    // 基准情况1：链表为空或递归到末尾，直接返回新节点
    if (current == null) {
        return new Node<>(data);
    }
    // 基准情况2：当前节点值大于插入值，新节点插在当前节点前
    if (data.compareTo(current.data) < 0) {
        Node<E> newNode = new Node<>(data);
        newNode.next = current;
        return newNode;
    }
    // 递归处理下一个节点，更新当前节点的next引用
    current.next = insertRecursive(current.next, data);
    return current;
}

逻辑说明 #

1. 对外接口保持单参数：主insert方法只接收要插入的数据data，内部调用带当前节点参数的私有辅助方法，把递归返回的结果重新赋值给head，既满足参数要求，又能处理插入表头的场景。
2. 基准情况对应迭代逻辑：
   • 当current为空时，对应迭代版中遍历到链表末尾的情况，直接返回新节点作为上一个节点的next。
   • 当插入数据小于当前节点值时，对应迭代版中插表头或找到插入位置的场景，创建新节点并挂载当前节点，返回新节点让上层递归更新链接。
3. 递归遍历替代循环：迭代版里的while循环找插入位置，换成递归深入current.next的过程，每次递归都会处理下一个节点，直到触发基准情况，再逐层返回更新链表链接。

这个实现完全匹配你迭代版的有序插入逻辑，同时对外只暴露单参数方法，解决了你之前的困惑。

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