关于程序员:剑指-Offer-II-029-排序的循环链表

题目形容

这是 LeetCode 上的 剑指 Offer II 029. 排序的循环链表 ，难度为 中等。

Tag :「链表」、「模仿」

给定循环枯燥非递加列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal，使这个列表依然是循环升序的。

给定的能够是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。

如果有多个满足条件的插入地位，能够抉择任意一个地位插入新的值，插入后整个列表依然放弃有序。

如果列表为空（给定的节点是 null），须要创立一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

示例 1：

输出：head = [3,4,1], insertVal = 2

输入：[3,4,1,2]

解释：在上图中，有一个蕴含三个元素的循环有序列表，你取得值为 3 的节点的指针，咱们须要向表中插入元素 2。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最初返回节点 3。

示例 2：

输出：head = [], insertVal = 1

输入：[1]

解释：列表为空（给定的节点是 null），创立一个循环有序列表并返回这个节点。

示例 3：

输出：head = [1], insertVal = 0

输入：[1,0]

提醒：

• $0 <= Number of Nodes <= 5 \times 10^4$
• $-10^6 <= Node.val <= 10^6$
• $-10^6 <= insertVal <= 10^6$

链表

这是一道惯例的链表模拟题。

为了不便，咱们记 insertVal 为 x，记 head 为 he。

起始咱们先将待插入的节点创立进去，记为 t，当 he 为空时，间接返回 t 即可。

因为咱们须要返回本来的头结点，因而咱们先应用变量 ans 对原始的 he 进行转存，随后复用 he 来充当游标进行遍历。

咱们先对链表进行一次实现遍历，遍历过程中保护节点最值 max 和 min，因为链表是循环的，咱们须要应用 he.next != ans 作为咱们循环的完结条件，含意为回到链表结尾。

此时依据最大值和最小值是否相等（即整段链表值是否统一）来进行分状况探讨：

• 若满足 max = min，此时指标节点 t 插入在哪个地位都满足条件，咱们间接将其与 ans 关联即可；

• 若不满 max = min，此时咱们先对链表进行一次遍历，找到有序列表的完结点（完结点的定义为：以后节点值为最大值，下一节点值为最小值。即为有序链表宰割地位的左端点），在依据「插入值 x 是否为新链表的最值」进行分状况探讨：

  • 若满足 $x >= max$ 或 $x <= min$，阐明指标节点 t 插入宰割地位即可；
  • 若不满足上述两条件，须要从宰割地位登程，找到指标插入地位，即满足 he.val <= x && x <= he.next.val 的地位。

代码：

class Solution {public Node insert(Node he, int x) {Node t = new Node(x);
        t.next = t;
        if (he == null) return t;
        Node ans = he;
        int min = he.val, max = he.val;
        while (he.next != ans) {
            he = he.next;
            min = Math.min(min, he.val);
            max = Math.max(max, he.val);
        }
        if (min == max) {
            t.next = ans.next;
            ans.next = t;
        } else {while (!(he.val == max && he.next.val == min)) he = he.next;
            while (!(x <= min || x >= max) && !(he.val <= x && x <= he.next.val)) he = he.next;
            t.next = he.next;
            he.next = t;
        }
        return ans;
    }
}

• 工夫复杂度：$O(n)$
• 空间复杂度：$O(1)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 剑指 Offer II 029 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

本文由 mdnice 多平台公布