如何在不修改节点指针的前提下高效交换循环链表的前后两半-java教程-PHP中文网

如何在不修改节点指针的前提下高效交换循环链表的前后两半

本文介绍一种时间复杂度为 O(n)、空间复杂度为 O(1) 的优雅解法：仅通过重定向 tail 引用即可完成循环链表前后半段的逻辑交换，无需修改任何节点的 next 指针。

本文介绍一种时间复杂度为 o(n)、空间复杂度为 o(1) 的优雅解法：仅通过重定向 `tail` 引用即可完成循环链表前后半段的逻辑交换，无需修改任何节点的 `next` 指针。

在循环链表中，“交换前后两半”本质上是重新定义逻辑起始点——即调整 tail 所指向的节点，使原链表从新 tail 的下一个节点开始遍历时，自然呈现出“后半段接前半段”的顺序。关键洞察在于：不需要改变任何节点的 next 链接关系，只需让 tail 指向原链表的“中点前驱”节点（即前半段的末尾节点），即可实现语义上的半段交换。

例如，对长度为 10 的链表 [v,w,t,j,q,o,w,s,w,t]（tail 指向末尾 t），其逻辑结构为循环：
v → w → t → j → q → o → w → s → w → t → (back to v)
若将 tail 改为指向 q（即第 5 个节点，索引从 0 起算），则新遍历起点为 q.next = o，得到序列 [o,w,s,w,t,v,w,t,j,q] —— 正是题目所求。

为精确定位该分割点，我们采用快慢指针法：

快指针（fast）每次走 2 步，慢指针（实际由 tail 充当）每次走 1 步；
初始时，令 fast = tail.next.next（跳过 tail 自身，从第二个节点开始），tail 先前移一步（tail = tail.next），作为慢指针起点；
循环条件为 fast != origTail && fast.next != origTail：确保快指针尚未绕回原始 tail（即未完成一圈），从而保证慢指针停在前半段末尾（即新 tail 应处位置）。

以下是完整、健壮的实现：

public void swapHalf() {
    // 空链表或单节点：无半段可交换
    if (tail == null || tail.next == tail) {
        return;
    }

    CharNode origTail = tail;         // 保存原始 tail 用于终止判断
    tail = tail.next;                 // 慢指针初始位置：从 head 开始（tail.next 即 head）
    CharNode fast = tail.next.next;   // 快指针起始：head 的 next.next

    // 快指针未绕回原 tail 前持续推进
    while (fast != origTail && fast.next != origTail) {
        fast = fast.next.next;
        tail = tail.next;
    }
    // 循环结束时，tail 恰好指向原前半段的最后一个节点
    // 因此 tail.next 即为新序列的首节点，语义上完成“半段交换”
}

✅ 正确性保障：

对偶数长度 n（如 10），快指针恰好绕行一圈（n 步）时，慢指针走了 n/2 步，停在第 n/2 个节点（索引 n/2−1），即前半段尾部；
对奇数长度 n（如 9），快指针在 n−1 步后触发 fast.next == origTail 条件退出，慢指针位于第 ⌊n/2⌋ 个节点（如第 4 个），仍满足“前半段结尾”语义（前 4 个 + 后 5 个）；
边界情况（0、1、2 节点）均被 if 条件覆盖，安全返回。

⚠️ 注意事项：