如何在单次遍历LinkedList时完成最小偶数后插入0的操作？

结论 #

你的需求完全可以在单次遍历中实现，你提出的自定义双向链表实现思路是正确的，只需补充少量边界处理即可。

1 Java自带LinkedList的单次遍历实现 #

由于Java标准库的LinkedList不对外暴露内部节点，我们可以借助ListIterator的特性实现单次遍历操作，核心逻辑是遍历过程中动态维护当前找到的最小偶数，发现更小的偶数时删除之前插入的0，在当前最小偶数后方重新插入0，所有迭代器操作均为O(1)复杂度，全程仅遍历一次列表：

LinkedList<Integer> list = new LinkedList<>();
list.add(4);
list.add(2);
list.add(5);

var itr = list.listIterator();
int minEven = Integer.MAX_VALUE;
boolean hasInserted = false;

while (itr.hasNext()) {
    int num = itr.next();
    if (num % 2 == 0 && num < minEven) {
        minEven = num;
        // 已插入过旧的0，先删除
        if (hasInserted) {
            itr.previous();
            itr.previous();
            itr.remove();
            itr.next();
        }
        // 在当前最小偶数后插入0
        itr.add(0);
        hasInserted = true;
    }
}

执行后列表结果为[4, 2, 0, 5]，符合预期。

2 自定义双向链表思路验证 #

你的原有思路逻辑正确，但存在两个边界漏洞，修复后即可正常运行：

• 初始smallest设为固定值节点会导致链表无偶数时异常，应该初始化为null
• 最小偶数是链表尾节点时，smallest.next为null，直接访问prev会触发空指针，需要增加非空判断

修复后伪代码如下：

Node smallest = null; // 初始为null，代表未找到偶数
Node current = head;
while (current != null){
   if (current.value % 2 == 0 && (smallest == null || current.value < smallest.value)){
      smallest = current;
   }
   current = current.next;
}

// 仅存在偶数时执行插入
if (smallest != null) {
    Node zero = new Node(0);
    zero.prev = smallest;
    zero.next = smallest.next;
    if (smallest.next != null) {
        smallest.next.prev = zero;
    }
    smallest.next = zero;
}

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