单栈辅助+单次遍历的单链表奇偶位置原地重排问题排查与修复

嘿，我一眼就看到你代码里的核心问题了——栈的后进先出（LIFO）特性搞乱了偶数节点的相对顺序！你把偶数节点按遍历顺序压栈，然后直接弹出连接，结果偶数节点的顺序完全反了：比如测试用例里的2、4，压栈后弹出是4、2，接到奇数链1->3->5后面就变成了1->3->5->4->2，这和你要的1->3->5->2->4完全不符，这就是你看到的“连接错误、节点丢失”的根本原因！

接下来我会帮你拆解问题，然后给出符合所有约束的修复方案，一步步讲清楚为什么这么做。

问题拆解：你的代码哪里出了问题？ #

1. 偶数节点顺序反转：栈是LIFO结构，你按2→4→6的顺序压栈，弹出时是6→4→2，直接连接会彻底破坏偶数节点的原相对顺序，这是最致命的错误。
2. 指针处理冗余且易出错：原代码提前断开所有节点的next指针，反而增加了指针错乱的风险；而且oddTail的初始化逻辑可以更简洁。
3. 循环风险：如果某个节点的next没有被正确置空或重连，可能会导致链表出现循环（比如原来的偶数节点的next还指向奇数节点，而那个奇数节点又在前面的链里）。

符合约束的修复方案 #

我们要解决的核心矛盾是：用单栈保存偶数节点，同时最后能恢复它们的原顺序。思路是：

• 单次遍历链表时，依然把偶数节点压入栈（满足单次遍历、单栈约束）。
• 遍历结束后，把栈中的节点反向连接成符合原顺序的偶数链：因为栈里的节点是倒序的，我们从栈顶弹出节点，依次将它们的next指向当前的偶数链头，最后就能得到原顺序的偶数链。
• 把偶数链接到奇数链的尾部，完成重排。

修复后的完整代码 #

class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedListRearranger {
    public ListNode rearrangeByPosition(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        Stack<ListNode> evenNodes = new Stack<>();
        ListNode current = head;
        ListNode oddTail = head; // 第一个节点是奇数，直接初始化为oddTail
        int position = 1;
        
        // 单次遍历：处理奇数节点，压入偶数节点
        while (current != null) {
            ListNode nextNode = current.next;
            if (position % 2 == 1) {
                // 处理奇数节点：仅更新oddTail（第一个节点已初始化）
                if (position != 1) {
                    oddTail.next = current;
                    oddTail = current;
                }
            } else {
                // 偶数节点压栈，同时断开与原链表的连接（避免循环）
                current.next = null;
                evenNodes.push(current);
            }
            current = nextNode;
            position++;
        }
        
        // 从栈中构建原顺序的偶数链
        ListNode evenHead = null;
        while (!evenNodes.isEmpty()) {
            ListNode node = evenNodes.pop();
            // 把当前节点作为新的evenHead，next指向原来的evenHead
            node.next = evenHead;
            evenHead = node;
        }
        
        // 把偶数链接到奇数链尾部
        oddTail.next = evenHead;
        // 确保最后一个节点的next为null（压栈时已处理，这里可以省略，但加了更稳妥）
        if (evenHead != null) {
            ListNode temp = evenHead;
            while (temp.next != null) temp = temp.next;
            temp.next = null;
        }
        
        return head;
    }
}

关键步骤详解 #

1. 遍历阶段的指针优化：

   • 直接把第一个节点（奇数位置）初始化为oddTail，避免了原代码中对oddTail == null的冗余判断，逻辑更简洁。
   • 仅在处理偶数节点时断开next指针，既避免了循环风险，又减少了不必要的指针操作。

2. 构建偶数链的核心逻辑：

   • 初始化evenHead为null，然后从栈顶弹出节点：
     比如栈里是2、4、6（push顺序2→4→6，栈顶是6）：
     • 弹出6，6.next = null（evenHead初始为null），evenHead = 6
     • 弹出4，4.next = 6，evenHead = 4
     • 弹出2，2.next = 4，evenHead = 2
   • 最终得到的evenHead就是2→4→6，完全符合原顺序。

3. 边界情况处理：

   • 空链表或单节点链表直接返回，无需额外处理。
   • 奇数长度的链表：最后一个节点是奇数，oddTail指向它，连接偶数链后，奇数链的尾指针正确指向偶数链头。
   • 偶数长度的链表：最后一个节点是偶数，压入栈后，构建的偶数链正确接到奇数链尾部。

验证测试用例 #

拿你提供的测试用例1→2→3→4→5来验证：

• 遍历后，奇数链是1→3→5，oddTail指向5；偶数栈里是2、4（push顺序2→4，栈顶是4）。
• 构建偶数链：弹出4→4.next=null，evenHead=4；弹出2→2.next=4，evenHead=2。
• 连接后：5.next=2，最终链表是1→3→5→2→4，完全符合预期。

为什么这个方案符合所有约束？ #

1. 单栈空间：只使用了一个栈，空间复杂度O(n/2)=O(n)，符合要求。
2. 单次遍历：仅用一个while循环遍历原链表，构建偶数链的循环是O(n/2)的线性操作，总时间复杂度O(n)，满足单次遍历的核心要求。
3. 原地修改：所有操作都是在原节点上修改指针，没有创建新节点。
4. 无其他数据结构：只用到了栈和几个指针变量。
5. 不依赖节点值：完全通过position判断位置，和节点值无关。

这样应该就能解决你遇到的所有问题了，你可以把这段代码拿去测试你的用例，应该都能得到正确结果！

备注：内容来源于stack exchange，提问作者Poojana Ometh