『LeetCode』剑指 Offer II 029 排序的循环链表

题目

给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 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 * 10^4\)
\(-10^6 <= Node.val <= 10^6\)
\(-10^6 <= insertVal <= 10^6\)

注意：本题与主站 708 题相同： https://leetcode-cn.com/problems/insert-into-a-sorted-circular-linked-list/(这个是会员题)

题解

【排序的循环链表】简单模拟

模拟

按照要求，只需遍历链表，找到满足 p.val <= insertVal <= p.next.val 的结点 p 然后在 p 后面插入新结点即可，但是注意有两种情况不存在这样的结点 p:

所有结点的值都相同或只有一个结点，且 p.val != insertVal, 这种情况所给结点插入任意位置均可以，只需判断是遍历指针是否回到 head 即可知道是否是这种情况
insertVal 大于链表所有结点值或小于链表结点值，这种情况插入点应当在最大结点后面和最小结点前面，但由于是循环链表，所以最大结点后面和最小结点前面实际上是同一个位置，即遍历链表中唯一一个不满足单调增加的点，找到这个点即可

除此之外，空链表的情况也需要特殊处理。

# Code language: Python
class Solution:
    def insert(self, head: 'Node', insertVal: int) -> 'Node':
        if head is None:
            head = Node(insertVal)
            head.next = head
            return head
        # 找 p.val <= insertVal <= p.next.val
        p = head
        while not (p.val <= insertVal <= p.next.val):
            p = p.next
            # 有两种情况找不到这样的位置
            # 一是给定值比所有结点值都大, 二是给定值比所有结点值都小
            # 这两种情况的插入位置都在链表唯一非递增的位置
            if p == head or (p.val > p.next.val and (insertVal >= p.val or insertVal <= p.next.val)):
                break
        p.next = Node(insertVal, p.next)
        return head

// Code language: Java
class Solution {
    public Node insert(Node head, int insertVal) {
        if (head == null) {
            Node ans = new Node(insertVal);
            ans.next = ans;
            return ans;
        }
        Node p = head;
        while (!(p.val <= insertVal && insertVal <= p.next.val)) {
            p = p.next;
            if (p == head || (p.val > p.next.val && (insertVal >= p.val || insertVal <= p.next.val)))
                break;
        }
        p.next = new Node(insertVal, p.next);
        return head;
    }
}

// Code language: C++
class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if (head == nullptr) {
            Node* ans = new Node(insertVal);
            ans->next = ans;
            return ans;
        }
        Node* p = head;
        while (!(p->val <= insertVal && insertVal <= p->next->val)) {
            p = p->next;
            if (p == head || (p->val > p->next->val && (insertVal >= p->val || insertVal <= p->next->val)))
                break;
        }
        p->next = new Node(insertVal, p->next);
        return head;
    }
};

// Code language: C#
public class Solution {
    public Node Insert(Node head, int insertVal) {
        if (head == null) {
            Node ans = new Node(insertVal);
            ans.next = ans;
            return ans;
        }
        Node p = head;
        while (!(p.val <= insertVal && insertVal <= p.next.val)) {
            p = p.next;
            if (p == head || (p.val > p.next.val && (insertVal >= p.val || insertVal <= p.next.val)))
                break;
        }
        p.next = new Node(insertVal, p.next);
        return head;
    }
}

// Code language: C
struct Node* insert(struct Node* head, int insertVal) {
    if (head == NULL) {
        struct Node* ans = (struct Node*) malloc(sizeof(struct Node));
        ans->val = insertVal;
        ans->next = ans;
        return ans;
    }
    struct Node* p = head, *tmp;
    while (!(p->val <= insertVal && insertVal <= p->next->val)) {
        p = p->next;
        if (p == head || (p->val > p->next->val && (insertVal >= p->val || insertVal <= p->next->val)))
            break;
    }
    tmp = p->next;
    p->next = (struct Node*) malloc(sizeof(struct Node));
    p = p->next;
    p->val = insertVal;
    p->next = tmp;
    return head;
}

时间复杂度: \(O(n)\)
空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』剑指 Offer II 029 排序的循环链表

题目

标签

题解

模拟