反转链表连续偶数构成的子段 现有代码运行超时如何解决

原有代码问题排查 #

• 逻辑完全不符合需求：原有代码将所有偶数的索引收集后，直接取第一个偶数和最后一个偶数的位置作为全局反转区间，会把区间内的奇数也一并反转，完全违背「仅反转连续偶数子段」的规则
• 方法调用错误：reverseMain中调用的reverseLinkedList方法不存在，实际定义的是reverseSubList，代码无法正常编译运行
• 反转逻辑存在指针拼接错误：子段反转后没有正确和前后的非偶数段节点拼接，极易导致链表出现环，遍历过程死循环是触发时间超限的核心原因
• 时间效率低：多次遍历链表查找子段位置，长链表场景下性能表现极差

正确实现思路 #

一次遍历链表即可完成所有操作，时间复杂度O(n)，空间复杂度O(1)：

1. 增加虚拟头节点统一处理头部就是偶数段的边界情况
2. 遍历过程中记录当前偶数段的前一个前驱节点
3. 遇到偶数时，开始反转当前连续偶数子段，直到遇到奇数或链表末尾
4. 将反转后的偶数段和前驱节点、后续节点正确拼接，继续遍历剩余节点

可运行正确代码 #

假设单链表节点定义如下：

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

功能实现代码：

public Node reverseEvenSubSegments(Node head) {
    // 虚拟头节点，统一处理头部为偶数段的边界场景
    Node dummy = new Node(-1);
    dummy.next = head;
    // prev存储当前偶数段的前一个非偶数节点
    Node prev = dummy;
    Node curr = head;

    while (curr != null) {
        // 匹配到连续偶数段起点
        if (curr.data % 2 == 0) {
            // 记录偶数段第一个节点，反转后会成为偶数段尾节点
            Node evenTail = curr;
            Node reversePrev = null;
            // 反转当前连续偶数段
            while (curr != null && curr.data % 2 == 0) {
                Node next = curr.next;
                curr.next = reversePrev;
                reversePrev = curr;
                curr = next;
            }
            // 拼接反转后的偶数段到原链表
            prev.next = reversePrev;
            evenTail.next = curr;
            // 更新前驱指针到偶数段尾节点，继续向后遍历
            prev = evenTail;
        } else {
            // 非偶数节点直接跳过
            prev = curr;
            curr = curr.next;
        }
    }
    return dummy.next;
}

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