[LeetCode] 708. Insert into a Cyclic Sorted List

qpwoeiru96 发布于2019-08-16 13:50 / 1792人阅读

Problem

Given a node from a cyclic linked list which is sorted in ascending order, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be a reference to any single node in the list, and may not be necessarily the smallest value in the cyclic list.

If there are multiple suitable places for insertion, you may choose any place to insert the new value. After the insertion, the cyclic list should remain sorted.

If the list is empty (i.e., given node is null), you should create a new single cyclic list and return the reference to that single node. Otherwise, you should return the original given node.

The following example may help you understand the problem better:

In the figure above, there is a cyclic sorted list of three elements. You are given a reference to the node with value 3, and we need to insert 2 into the list.

The new node should insert between node 1 and node 3. After the insertion, the list should look like this, and we should still return node 3.

Solution

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;

    public Node() {}

    public Node(int _val,Node _next) {
        val = _val;
        next = _next;
    }
};
*/
class Solution {
    public Node insert(Node head, int insertVal) {
        if (head == null) {
            head = new Node();
            head.val = insertVal;
            head.next = head;
            return head;
        }
        Node next = head.next, pre = head;
        while (next != head) {
            //insert in flat or rising range
            if (pre.val == insertVal || (pre.val < insertVal && insertVal < next.val)) {
                Node cur = new Node(insertVal, next);
                pre.next = cur;
                return head;
            }
            //insert in peak and falling range
            if (pre.val > next.val && (insertVal < next.val || insertVal > pre.val)) {
                Node cur = new Node(insertVal, next);
                pre.next = cur;
                return head;
            }
            
            pre = next;
            next = next.next;
        }
        //insert before head
        Node cur = new Node(insertVal, next);
        pre.next = cur;

        return head;
    }
}

私有云海外云主机 insert_into_select Cyclic v708 Sorted

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72404.html

[LintCode] Insert into a Cyclic Sorted List

Problem Given a node from a cyclic linked list which has been sorted, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be any single node ...

Acceml 2019-08-15 13:27 评论0 收藏0
[LeetCode] 23. Merge k Sorted Lists

摘要：思路这题中的中，个还有其中个别的等于的情况，所以要判断一下再加入代码 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Heap Time Complexity: Update the heap costs O(nklogk) Space ...

Codeing_ls 2019-08-15 12:25 评论0 收藏0
leetcode--57--Insert Interval

摘要：问题描述分析这道题的关键在于理解问题，抽取原型，理解中间可以部分如何界定，以及非部分如何进行追加。需要注意的是循环到最后一个元素和在最后一个元素的区别。问题描述： Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You m...

kycool 2019-07-31 11:04 评论0 收藏0
[LeetCode] Insert Interval

Problem Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times....

Jonathan Shieber 2019-08-19 11:08 评论0 收藏0
leetcode57. Insert Interval

摘要：题目要求给定一组顺序排列且相互之间没有重叠的区间，输入一个区间，将它插入到当前的区间数组中，并且将需要合并的区间合并，之后返回插入并且合并后的区间。我们将这三个类型的区间分别标注为类型，类型，类型。题目要求 Given a set of non-overlapping intervals, insert a new interval into the intervals (merge...

Yuanf 2019-08-16 10:37 评论0 收藏0