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

Categories:

题目描述
思路分析
1. 解法一：一次遍历插入（推荐）
相似题目

题目描述

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

思路分析

解法一：一次遍历插入（推荐）

核心思路：

空链表直接创建新节点并自环。

遍历循环链表寻找插入点，满足正常升序区间或断点区间之一即可插入：正常升序 cur.val <= insertVal <= cur.next.val；断点区间 cur.val > cur.next.val 且插入值位于两端之外。

若一圈未命中（值全相等），在当前位置插入即可。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(1)，仅使用常数额外指针。

class Solution {
    public Node insert(Node head, int insertVal) {
        Node node = new Node(insertVal);
        if (head == null) {
            node.next = node;
            return node;
        }

        Node cur = head;
        while (true) {
            Node next = cur.next;

            // 正常升序区间
            if (cur.val <= insertVal && insertVal <= next.val) {
                cur.next = node;
                node.next = next;
                return head;
            }

            // 断点区间：最大值到最小值
            if (cur.val > next.val && (insertVal >= cur.val || insertVal <= next.val)) {
                cur.next = node;
                node.next = next;
                return head;
            }

            cur = next;
            if (cur == head) {
                break;
            }
        }

        // 全部节点值相等，插入任意位置
        node.next = head.next;
        head.next = node;
        return head;
    }
}

func insert(head *Node, insertVal int) *Node {
    node := &Node{Val: insertVal}
    if head == nil {
        node.Next = node
        return node
    }

    cur := head
    for {
        next := cur.Next

        // 正常升序区间
        if cur.Val <= insertVal && insertVal <= next.Val {
            cur.Next = node
            node.Next = next
            return head
        }

        // 断点区间：最大值到最小值
        if cur.Val > next.Val && (insertVal >= cur.Val || insertVal <= next.Val) {
            cur.Next = node
            node.Next = next
            return head
        }

        cur = next
        if cur == head {
            break
        }
    }

    // 全部节点值相等，插入任意位置
    node.Next = head.Next
    head.Next = node
    return head
}

相似题目

题目	难度	考察点
21. 合并两个有序链表	简单	链表遍历
83. 删除排序链表中的重复元素	简单	有序链表
86. 分隔链表	中等	双指针
148. 排序链表	中等	归并排序
234. 回文链表	简单	快慢指针

本文作者: HGNULB

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