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

2026-03-28 HGNULB 约 5 分钟

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

分类

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

标签

LCR 链表

题目描述

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

题意分析

给定循环单链表上的任意入口，将一个新值插入，同时保持绕环的非递减顺序。允许重复值，非空链插入后仍返回原入口，不要求入口指向最小节点。

如果原环包含不同值，恰有一条从最大值回到最小值的下降边，其余边均非递减；全等环没有下降边。空链需创建一个新节点并让它指向自己，成为长度一的环。

解法：遍历一圈寻找合法插入位置

核心思路

[!blue]

只需要找到一对相邻节点并把新节点接在中间。普通非递减边满足 prev.val <= value <= next.val 时可以插入，两条新边仍保持非递减，等号允许放入重复值。

对下降边 prev.val > next.val，前一个节点是最大值，后一个是最小值。若新值不小于最大值，或者不大于最小值，把它放在这条边中间后仍只有一个最大到最小的回转，因此同样合法。

这两类位置能覆盖所有非全等环：值处于现有极值之间时，总有普通相邻边夹住它；值在极值范围外时，可放到下降边。若全环相等，新值相同时普通边即可命中，不同时插在任意边都能形成合法回转。

环上不会遇到空，必须以回到入口作为最迟终止条件。Java 逐边检查，并在当前后继等于 head 时兜底插入；Go 在来到指回 head 的最后一条边时结束扫描并插入。若此前都没有合适位置，非全等环的合法位置必在这条尚未处理的回头边，全等环则任意边都合法，因此都能正确结束。

接线时要保留旧后继。Java 先把 p.next 存到新节点的后继再改 p.next；Go 已经用 curr 独立保存后继，所以先连 prev.Next 再连 node.Next 也安全。需要保护的是旧引用，而不是机械规定所有实现都使用同一种赋值顺序。

解题步骤

1. 创建新节点；若原链为空，让新节点自环并返回。
2. 从给定入口开始检查相邻边，不假定入口是最小值。
3. 普通边检查新值是否夹在两端之间，下降边检查是否为可接入的极值。
4. 命中即插入；扫描回入口前仍未命中时，在最后一条边兜底插入。
5. 非空链统一返回原 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)$，至多绕环一圈，每条边只做常数次比较。
• 空间复杂度：$O(1)$，只新建要求插入的节点，并使用固定数量的游标。

关键点总结

[!green]

• 非全等环有一条下降边，全等环没有下降边，不能一律说恰有一个下降点。
• 普通区间容纳范围内的值，最大到最小的边容纳新的极值。
• 回到入口提供有限终止条件，也覆盖单节点和全等环。
• 保留旧后继即可安全插入，原入口不改变。

易错点总结

[!yellow]

• 假设 head 就是最小节点，会误判经过最大值回转后的局部顺序。
• 只用严格不等式，会漏掉合法的重复值插入位置。
• 下降边条件要同时考虑新最大和新最小，两种情况使用逻辑或。
• 没有绕圈终止条件，在全等环且插入不同值时可能一直找不到普通区间。
• 覆盖连接前必须保存旧后继；若已有独立的 curr，则不需要再次读取被覆盖的 prev.Next。
• 空链的新节点必须指向自身，不能留下空后继。

相似题目

题目	难度	关联与区别
147. 对链表进行插入排序	中等	同样在有序链表中寻找插入位置，本题是环，还要识别最大值到最小值的交界。
21. 合并两个有序链表	简单	同样依赖链表局部有序关系连接节点，本题不能用遇到null作为扫描终点。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/32114199

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！