LeetCode LCR 029. 循环有序列表的插入

2026-03-28 HGNULB 约 8 分钟

文章信息 5 个分类 2 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 029. 循环有序列表的插入

题意分析

给定一个循环单链表的任意一个节点 head，链表中的值按非递减顺序排列（绕一圈后回到最小值），要求把 insertVal 插进去并保持这个循环有序性，返回原来的 head（若原链表为空则返回新建的自环节点）。

「循环有序」和「有序」差别很大。普通有序链表从头到尾单调不减，而循环链表被从某处切开成环后，序列里恰好存在一个下降点：前一个值大于后一个值，那里就是「最大值 → 最小值」的接缝。给定的 head 是任意节点，不保证是最小值，所以不能假设从 head 出发就是升序。

由此，合法的插入位置只有三类：夹在两个相邻且满足 prev.val <= insertVal <= curr.val 的节点之间；比全局最大还大或比全局最小还小，那就插在接缝处；以及所有节点值都相同（此时根本没有下降点），插在任意位置都合法。

边界要覆盖：head 为空（要新建一个指向自己的节点）；链表只有一个节点；链表所有值相等且插入值不在其中——这种情况绕一圈都找不到严格意义上的「槽位」，必须有一个兜底出口，否则会死循环。

「返回原 head」这条要求意味着插入不会改变入口，只需就地接线。

解法：LCR处理

核心思路

暴力想法是把所有值取出来排序再重建，但链表可能很长，且题目本来就有序，重建纯属浪费；更关键的是这样丢掉了「就地插入」的本意。

换个角度：既然只有一个下降点，那么从 head 出发绕一圈就足以看到全部相邻对，插入位置一定在其中之一。于是问题变成——逐对检查相邻节点 (p, p.next)，判断 insertVal 是否该落在这一对之间。

判定条件拆成三条互斥的情形，正好对应上面分析出的三类合法位置。

第一条，p.val <= insertVal && insertVal <= p.next.val。这是最普通的升序区间，插入值夹在中间。用非严格不等号是为了让重复值也能落进来。

第二条，p.val > p.next.val，说明 p 是全局最大、p.next 是全局最小，这一对就是接缝。此时只要 insertVal >= p.val（比最大还大）或 insertVal <= p.next.val（比最小还小），都应该插在接缝处。

第三条，p.next == head，表示已经绕完整整一圈仍未命中前两条。能走到这里只有一种可能：链表中所有值都相等（没有下降点），且插入值不等于它们。此时插在任何位置都保持循环有序，直接插在当前位置即可。这条兜底是循环能终止的保证。

循环不变量因此是：每一轮开始时，head 到 p 之间的所有相邻对都已被检查且都不是合法插入位置。由于第三条保证绕满一圈必然命中，循环最多走 n 步就结束。

空链表单独处理：新建节点让它 next 指向自己，构成长度为 1 的循环链表，然后返回这个新节点——这是唯一一种返回值不是原 head 的情况。

解题步骤

建节点并处理空链表：node = new Node(insertVal)，若 head == null 则 node.next = node 后直接返回 node。这一步必须放在最前面，否则后面访问 head.val 会空指针；同时它也是唯一改变返回值的分支。

从 head 起步逐对检查：p = head，用无限循环配合内部 break，因为终止条件是「命中某一类插入位置」而不是简单的指针走空——循环链表里指针永远不会变成空。

判定三条件的析取：三条用 || 连接，命中任意一条就在 p 与 p.next 之间插入。三者的顺序不影响正确性，但把兜底的 p.next == head 放在最后更符合语义——只有前两条都失败才轮到它。

插入并跳出：node.next = p.next; p.next = node; break;。两句顺序不能反，先改 p.next 会让 node.next 指向自己，链表就此断成两段。

推进：未命中则 p = p.next，继续检查下一对。

返回 head：原入口没有变化。Go 版把游标拆成 prev 与 curr 两个变量，用 curr != head 作为绕满一圈的终止条件，退出后在 prev 与 curr 之间插入，与 Java 版的三条件判定完全等价。

以 head = 3 → 4 → 1 →（回到 3）、insertVal = 2 走一遍。第一轮 p = 3：第一条要求 3 <= 2，不成立；第二条要求 3 > 4，不成立；第三条 p.next 是 4 而不是 head，不成立；p 推进到 4。第二轮 p = 4：第一条 4 <= 2 不成立；第二条 4 > 1 成立，但还要满足 2 >= 4 或 2 <= 1，两者都不成立；第三条 p.next 是 1 不是 head；p 推进到 1。第三轮 p = 1：第一条 1 <= 2 && 2 <= 3 成立，插入，得到 3 → 4 → 1 → 2 →（回到 3），绕一圈读出 1, 2, 3, 4，有序。

再看插在接缝的用例 insertVal = 5：第一轮 p = 3 三条都不成立；第二轮 p = 4 时第二条 4 > 1 成立且 5 >= 4 成立，插在 4 与 1 之间，得到 3 → 4 → 5 → 1，绕圈读出 1, 3, 4, 5，正确。同理 insertVal = 0 会在同一位置命中 0 <= 1 这一支。

最后看全等值用例 head = 3 → 3 → 3、insertVal = 2：三轮里第一条都要求 3 <= 2，恒不成立；第二条要求 3 > 3，恒不成立；直到 p 走到最后一个 3 时 p.next == head 成立，插入并跳出。如果没有这条兜底，指针会在环里无限打转直接超时。

代码实现

class Solution {
    public Node insert(Node head, int insertVal) {
        Node node = new Node(insertVal);
        // 空链表要自成一环，这是唯一返回值不是原 head 的分支。
        if (head == null) {
            node.next = node;
            return node;
        }
        Node p = head;
        for (;;) {
            // 三种合法位置：普通升序区间、最大到最小的接缝、绕满一圈的兜底。
            if (p.val <= insertVal && insertVal <= p.next.val
                || p.val > p.next.val && (insertVal <= p.next.val || insertVal >= p.val)
                || p.next == head) {
                node.next = p.next;
                p.next = node;
                break;
            }
            p = p.next;
        }
        return head;
    }
}

func insert(head *Node, x int) *Node {
    node := &Node{Val: x}
    // 空链表要自成一环，这是唯一返回值不是原 head 的分支。
    if head == nil {
        node.Next = node
        return node
    }
    prev, curr := head, head.Next
    // curr 回到 head 即绕满一圈，等价于 Java 版的兜底条件。
    for curr != head {
        if (prev.Val <= x && x <= curr.Val) || (prev.Val > curr.Val && (x >= prev.Val || x <= curr.Val)) {
            break
        }
        prev, curr = curr, curr.Next
    }
    prev.Next = node
    node.Next = curr
    return head
}

复杂度分析

时间复杂度：$O(n)$，n 为链表节点数。最坏情况（所有值相等）要绕满一圈才命中兜底条件，每个节点只被检查一次，判定本身是常数次比较。

空间复杂度：$O(1)$，除了必须新建的那一个节点外，只用了一两个游标指针，与链表长度无关。

关键点总结

循环有序链表的结构特征是「有且只有一个下降点」，把这句话写在纸上，三类插入位置自然就浮出来了——先刻画结构再写条件，比对着样例凑条件可靠得多。

接缝处的判定要写成 insertVal >= 最大 || insertVal <= 最小 的析取，两侧是同一个位置的两种成因，漏掉任何一支都会让极值插错地方。

环形结构的遍历必须自带终止条件，「绕回起点」就是它的「走到空」；任何在环上写循环的题都要先想清楚出口在哪。

全等值链表是本题唯一的死循环来源，它不是普通的边界而是必须存在的兜底分支，属于「不写就必挂」的一类。

插入时先接 node.next 再改 prev.next，这个先后顺序是所有链表插入的通用铁律。

面试视角：面试官最想听到的是「为什么恰好是这三种情况，且它们覆盖完全」。可以按「插入值落在某个升序区间内 / 落在区间外（即超出全局极值）/ 根本不存在区间（全等值）」三分法论证互斥且完备，比逐条罗列条件更有说服力。

易错点总结

漏掉 p.next == head 的兜底：3 → 3 → 3 插入 2 时前两条永远不成立，指针在环里无限打转，直接超时。

接缝条件只写 insertVal >= p.val：3 → 4 → 1 插入 0 时无法命中，绕一圈后靠兜底插在末尾，虽然本例侥幸正确，但换成 1 → 3 → 5 插入 0 会落到 5 与 1 之外的错误位置。

第一条用严格不等号 p.val < insertVal < p.next.val：1 → 3 → 5 插入 3 时所有区间都不命中，只能靠兜底插到末尾，破坏有序性。

忘记处理 head == null：直接访问 head.val 抛空指针异常。

空链表时只 return node 而不建自环：返回的节点 next 为空，不再是循环链表，后续遍历会崩。

插入时先写 p.next = node 再写 node.next = p.next：node.next 变成指向自己，3 → 4 → 1 插入 2 后链表从节点 2 处断成孤环。

用 while (p != head) 作循环条件却从 p = head 起步：循环体一次都不执行，任何输入都直接跳到插入逻辑，位置全错。

误以为 head 一定是最小值而从它开始按升序单调判断：给定入口是任意节点，3 → 4 → 1 这种输入会把 2 插到 3 之前，破坏循环有序。

插入后返回 node 而不是 head：题目要求返回原入口，非空链表时返回新节点会被判错。

相似题目

题目	难度	考察点
147. 对链表进行插入排序	中等	同样是「找槽位再接线」，但要对每个节点重复一次，且链表非循环
21. 合并两个有序链表	简单	也是往有序链里放节点，但源头是另一条有序链，靠双指针推进而非绕圈查找
35. 搜索插入位置	简单	同样求插入下标，但载体是可随机访问的有序数组，可用二分而非线性扫描
61. 旋转链表	中等	也要把链表接成环再断开，练的是同一套「环上定位」的手感
141. 环形链表	简单	环的存在性判定，提醒环形结构上任何遍历都必须自带终止条件
148. 排序链表	中等	从零把链表排成有序，是本题「维持有序」这一前提的上游问题