自定义Linked List：如何实现递归有序插入方法

我来帮你搞定这个递归插入的问题！之前你已经通过插入实现过排序，转递归的核心就是找准终止条件和每一步的递归逻辑，咱们一步步拆解：

1. 先定义基础的Pokemon和链表节点类 #

首先得把基础结构搭起来，这部分应该和你之前实现的差不多：

class Pokemon {
    String name;
    int level;

    public Pokemon(String name, int level) {
        this.name = name;
        this.level = level;
    }

    @Override
    public String toString() {
        return name + "(" + level + ")";
    }
}

class ListNode {
    Pokemon data;
    ListNode next;

    public ListNode(Pokemon data) {
        this.data = data;
        this.next = null;
    }
}

2. 自定义链表的递归插入实现 #

递归的关键是用一个辅助方法来处理节点的遍历和插入，因为插入操作可能会改变头节点（比如插入等级比所有节点都小的Pokemon），所以辅助方法需要返回更新后的节点链：

class CustomLinkedList {
    private ListNode head;

    // 对外暴露的插入方法，调用递归辅助函数
    public void insertByLevelRecursive(Pokemon newPokemon) {
        head = insertRecursiveHelper(head, newPokemon);
    }

    // 核心递归辅助方法
    private ListNode insertRecursiveHelper(ListNode current, Pokemon newPokemon) {
        // 终止条件1：当前节点为空，说明到了链表末尾，直接返回新节点
        if (current == null) {
            return new ListNode(newPokemon);
        }

        // 终止条件2：当前节点等级大于新Pokemon，把新节点插在当前节点前面
        if (current.data.level > newPokemon.level) {
            ListNode newNode = new ListNode(newPokemon);
            newNode.next = current;
            return newNode;
        }

        // 否则继续递归处理下一个节点，更新当前节点的next指向
        current.next = insertRecursiveHelper(current.next, newPokemon);
        return current;
    }

    // 打印链表，方便验证结果
    public void printList() {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("null");
    }
}

3. 逻辑解释 #

咱们拿你举的例子（插入Pigeon(6)）来走一遍流程：

• 初始链表：Bulbasaur(5) -> Squirtle(15) -> Charmander(20)
• 第一次递归：current是Bulbasaur(5)，5 < 6，所以递归处理current.next（Squirtle(15)）
• 第二次递归：current是Squirtle(15)，15 > 6，所以创建新节点Pigeon(6)，让它的next指向Squirtle，返回这个新节点
• 回到第一次递归：把Bulbasaur的next指向刚才返回的Pigeon节点，返回Bulbasaur
• 最终链表就变成了：Bulbasaur(5) -> Pigeon(6) -> Squirtle(15) -> Charmander(20)

4. 测试代码 #

你可以用这段代码验证效果：

public class Main {
    public static void main(String[] args) {
        CustomLinkedList list = new CustomLinkedList();
        // 插入初始节点
        list.insertByLevelRecursive(new Pokemon("Bulbasaur", 5));
        list.insertByLevelRecursive(new Pokemon("Squirtle", 15));
        list.insertByLevelRecursive(new Pokemon("Charmander", 20));
        
        System.out.println("插入前的链表：");
        list.printList();

        // 插入Pigeon
        list.insertByLevelRecursive(new Pokemon("Pigeon", 6));
        System.out.println("插入Pigeon后的链表：");
        list.printList();
    }
}

运行后输出：

插入前的链表：
Bulbasaur(5) -> Squirtle(15) -> Charmander(20) -> null
插入Pigeon后的链表：
Bulbasaur(5) -> Pigeon(6) -> Squirtle(15) -> Charmander(20) -> null

注意事项 #

• 一定要让辅助方法返回更新后的节点，不然会出现节点丢失的情况（比如插入头节点前的新节点时，必须更新链表的head）
• 递归终止条件要覆盖两种情况：链表末尾、找到第一个比新节点等级高的节点
• 如果有等级相同的情况，你可以根据需求调整判断逻辑（比如改成>=把相同等级的插在前面，或者>插在后面）

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