请教：基于迭代器的双向链表插入排序实现是否正确？

首先明确：你的实现思路属于插入排序——核心逻辑是逐个将原链表元素插入到已排序链表的对应位置，完全契合插入排序的核心特征。但代码存在几个关键bug导致排序失效，下面逐一分析并修复：

1. 空链表时的迭代器访问错误 #

当sortedList为空时，List.Iter.last(sortedList)返回的是链表的尾哨兵迭代器（无对应节点），此时调用curIndex.key_data()会触发空指针异常，直接导致第一个元素无法正常插入，你循环里的打印语句也会因此报错。

2. 插入位置的逻辑冗余问题 #

当当前元素比已排序链表的最后一个元素大时，无需循环调用next()（last迭代器的next()会直接到结束位置），直接插入到last之后即可，原代码的循环属于冗余操作。

修复后的代码 #

public static List sort(List list) {        
    List sortedList = new List();                 
    List.Iter curIndex;
                
    for(List.Iter iter = List.Iter.first(list); !iter.end(); iter.next()) {
        List.Node node = iter.key_data();  
        System.out.println("node: "+node.data);

        if (sortedList.empty()) {                
            // 空链表直接插入初始位置
            curIndex = List.Iter.last(sortedList);
            sortedList.insAfter(curIndex, node.key, node.data);                
        } else {
            curIndex = List.Iter.last(sortedList);
            System.out.println("curIndex: "+curIndex.key_data().data);
            
            if (curIndex.key_data().key >= node.key) {
                // 向前查找第一个小于当前节点key的位置
                boolean hasPrev = true;
                while (hasPrev && curIndex.key_data().key >= node.key) {
                    hasPrev = curIndex.prev();                    
                }                                
                sortedList.insAfter(curIndex, node.key, node.data);                        
            } else {                            
                // 直接插入已排序链表末尾
                sortedList.insAfter(curIndex, node.key, node.data);                
            }
        }
    }
    return sortedList;
}

额外优化建议 #

• 移除调试用的打印语句，避免空指针风险。
• 可根据当前元素大小选择从头部或尾部开始查找插入位置，小幅提升查找效率（插入排序整体时间复杂度仍为O(n²)，属于正常范围）。

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