[LintCode] Insert into a Cyclic Sorted List

Acceml 发布于2019-08-15 13:27 / 984人阅读

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 in the list. Return the inserted new node.

Notice

3->5->1 is a cyclic list, so 3 is next node of 1.
3->5->1 is same with 5->1->3

Example

Given a list, and insert a value 4:
3->5->1
Return 5->1->3->4

Tags

Amazon Linked List

Solution

public class Solution {
    public ListNode insert(ListNode node, int x) {
        ListNode head = node;
        if (node == null) {
            node = new ListNode(x);
            node.next = node;
            return node;
        }
        if (node.next == head) {
            insertNode(node, x);
            return head;
        }
        while (node != null && node.next != null) {
            if (node.val < node.next.val) {
                if (node.val <= x && x <= node.next.val) {
                    insertNode(node, x);
                    break;
                }
            } else if (node.val > node.next.val) {
                if (x >= node.val || x <= node.next.val) {
                    insertNode(node, x);
                    break;
                }
            } else {
                if (node.next == head) {
                    insertNode(node, x);
                    break;
                }
            }
            node = node.next;
        }
        return head;
    }
    public void insertNode(ListNode head, int x) {
        ListNode node = new ListNode(x);
        node.next = head.next;
        head.next = node;
    }
}

GPU云服务器云服务器 insert_into_select Cyclic LintCode Sorted

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

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

[LeetCode] 708. Insert into a Cyclic Sorted List

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 r...

qpwoeiru96 2019-08-16 13:50 评论0 收藏0
[LintCode] Insert Node in Sorted Linked List

Problem Insert a node in a sorted linked list. Example Given list = 1->4->6->8 and val = 5. Return 1->4->5->6->8. Solution public class Solution { public ListNode insertNode(ListNode head, int val...

littleGrow 2019-08-15 13:24 评论0 收藏0
[LintCode/LeetCode] Find Median From / Data Stream

摘要：建立两个堆，一个堆就是本身，也就是一个最小堆另一个要写一个，使之成为一个最大堆。我们把遍历过的数组元素对半分到两个堆里，更大的数放在最小堆，较小的数放在最大堆。同时，确保最大堆的比最小堆大，才能从最大堆的顶端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...

zxhaaa 2019-08-14 14:35 评论0 收藏0
[LintCode/LeetCode] Merge Sorted Array

Problem Given two sorted integer arrays A and B, merge B into A as one sorted array. Notice You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements ...

summerpxy 2019-08-14 15:41 评论0 收藏0
[LintCode] Merge Sorted Array II

摘要：循环里最好先考虑和其中之一已经处理完的情况，就直接顺序放另一个没处理完的即可。然后再在里展开方法。避免其中一个数组较小会浪费效率的情况。丫把参数又换成了。。。 Problem Merge two given sorted integer array A and B into a new sorted integer array. Example A=[1,2,3,4] B=[2,4,5...

宠来也 2019-08-14 15:12 评论0 收藏0