Java中高效排序关联TodoEntity列表的最优方法

嘿，你现在的实现本质是冒泡排序的变种，时间复杂度是O(n²)——数据量小的时候还能凑合用，但数据量大（比如上千条）的时候会慢得离谱。咱们换个更高效的思路，用哈希表构建映射关系，直接把链表串起来，时间复杂度能降到O(n)，这才是最快的方式。

为什么你的当前实现效率低？ #

你的代码里每次循环都要调用getIndex遍历列表找位置，而且LinkedList.get(i)本身就是O(n)的操作，再加上频繁的remove和add，整个过程相当于每次都要遍历大半列表，数据量越大，耗时增长得越快。

最优思路详解 #

核心思路是用哈希表提前把节点之间的关联关系存起来，避免反复遍历：

1. 构建两个映射：
   • 一个用id做key，存对应的TodoEntity，用来快速查找任意id对应的节点。
   • 另一个用previousId做key，存对应的TodoEntity，用来快速找到以某个id为前驱的节点。
2. 找到链表的头节点：头节点是没有前驱的节点——也就是不存在任何节点的id等于它的previousId。
3. 从头节点开始串联链表：根据previousId的映射，依次找到下一个节点，直到链表结束。

具体代码实现 #

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TodoSorter {
    public static List<TodoEntity> sortTodos(List<TodoEntity> unsorted) {
        // 1. 构建id到实体的映射，O(n)时间
        Map<Integer, TodoEntity> idToEntityMap = new HashMap<>();
        // 2. 构建previousId到实体的映射，O(n)时间
        Map<Integer, TodoEntity> previousIdToEntityMap = new HashMap<>();
        
        for (TodoEntity todo : unsorted) {
            idToEntityMap.put(todo.getId(), todo);
            previousIdToEntityMap.put(todo.getPreviousId(), todo);
        }

        // 3. 找到头节点：没有任何实体的id等于它的previousId
        TodoEntity head = null;
        for (TodoEntity todo : unsorted) {
            if (!idToEntityMap.containsKey(todo.getPreviousId())) {
                head = todo;
                break;
            }
        }

        // 4. 从头节点开始串联整个链表，O(n)时间
        List<TodoEntity> sortedList = new ArrayList<>(unsorted.size());
        TodoEntity current = head;
        while (current != null) {
            sortedList.add(current);
            // 下一个节点的previousId等于当前节点的id，所以用当前id去映射里找
            current = previousIdToEntityMap.get(current.getId());
        }

        return sortedList;
    }
}

// 补充TodoEntity的getter方法（假设你已有这些方法）
class TodoEntity {
    private int id;
    private int previousId;

    public int getId() {
        return id;
    }

    public int getPreviousId() {
        return previousId;
    }

    // 构造方法、setter等其他代码...
}

关键优势 #

• 时间效率：三次线性遍历+哈希表的O(1)操作，整体时间复杂度是O(n)，比你当前的O(n²)实现快几个数量级。
• 代码简洁：逻辑清晰，没有嵌套循环和复杂的列表操作，更容易维护和排查问题。

边界情况说明 #

• 如果输入包含多个独立的链表（多个头节点），可以在找头节点时收集所有头节点，然后依次串联每个链表加入结果。
• 如果输入有环（比如节点A的previousId指向节点B，节点B的previousId指向节点A），需要加个visited集合防止无限循环，但你的场景应该是无环的待排序列表，所以暂时不需要考虑。

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