http://www.cnblogs.com/grandyang/p/9981163.html
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.
http://hehejun.blogspot.com/2018/09/leetcodeinsert-into-cyclic-sorted-list.html
思路很直观，注意edge case，大概有以下几种情况：
这道题就是要把所有的case都想清楚。
1：如果node就是null，需要造一个新的node，并且自己和自己连上。
除去以上的case，我们需要在这个链表里找到需要插入的点的位置。我们遍历链表，并且进行不同case的分析。
2：如果node.val < node.next.val，那么如果x在这里两个值当中，我们就可以把x插进去。
3：如果node.val > node.next.val，这说明现在我们在链表的环的最后一个节点。那么如果x比整个链表中最大的节点值node.val还大，或者比整个链表中最小的节点值node.next.val还小，那么x可以插在这两个当中。
4：如果node.val == node.next.val，那么我们还是要判断一下node是不是就是环的最后一个节点，以及node.next是不是环的头。如果是这样，我们可以把x插进去。
https://blog.csdn.net/sinat_32547403/article/details/78510434
https://segmentfault.com/a/1190000017139433
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.
思路很直观，注意edge case，大概有以下几种情况：
- list为空，我们新建node，并且将next指向自身
- 如果insertVal在某处节点curr满足，curr->val <= insertVal <= curr->next->val，insertVal插入curr之后
- 如果2中的情况没有出现，说明当前插入值是新的最大/最小值，我们需要在当前最大值对应的节点(有多个的话选最靠后的一个)之后插入
Node* insert(Node* head, int insertVal) {
if (!head)
{
Node* node = new Node(insertVal, nullptr);
node->next = node;
return node;
}
Node* curr = head, *maxNode = head;
bool inserted = false;
while(true)
{
if (curr->next->val < curr->val)
maxNode = curr;
if (curr->next->val >= insertVal && curr->val <= insertVal)
{
Node* node = new Node(insertVal, curr->next);
curr->next = node;
inserted = true;
break;
}
curr = curr->next;
if (curr == head)break;
}
//turning point from max to min
if (!inserted)
{
Node* node = new Node(insertVal, maxNode->next);
maxNode->next = node;
}
return head;
}
https://yeqiuquan.blogspot.com/2017/04/lintcode-599-insert-into-cyclic-sorted.html这道题就是要把所有的case都想清楚。
1：如果node就是null，需要造一个新的node，并且自己和自己连上。
除去以上的case，我们需要在这个链表里找到需要插入的点的位置。我们遍历链表，并且进行不同case的分析。
2：如果node.val < node.next.val，那么如果x在这里两个值当中，我们就可以把x插进去。
3：如果node.val > node.next.val，这说明现在我们在链表的环的最后一个节点。那么如果x比整个链表中最大的节点值node.val还大，或者比整个链表中最小的节点值node.next.val还小，那么x可以插在这两个当中。
4：如果node.val == node.next.val，那么我们还是要判断一下node是不是就是环的最后一个节点，以及node.next是不是环的头。如果是这样，我们可以把x插进去。
public ListNode insert(ListNode node, int x) { if (node == null) { node = new ListNode(x); node.next = node; return node; } ListNode head = node; 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 { // node.val == node.next.val if (node.next == head) { insertNode(node, x); break; } } node = node.next; } return head; } public void insertNode(ListNode node, int x) { ListNode newNode = new ListNode(x); newNode.next = node.next; node.next = newNode; }
https://blog.csdn.net/sinat_32547403/article/details/78510434
public ListNode insert(ListNode node, int x) {
// write your code here
ListNode n = new ListNode(x);
if (node == null) {
n.next = n;
return n;
}
ListNode curr = node.next;
ListNode prev = node;
while (curr != node) {
if (prev.val <= x && curr.val >= x) {
break;
}
if (prev.val > curr.val && (prev.val < x || curr.val > x)) {
break;
}
curr = curr.next;
prev = prev.next;
}
prev.next = n;
n.next = curr;
return node;
}
这道题让我们在循环有序的链表中插入结点，要求插入结点后，链表仍保持有序且循环。题目中强调了corner case的情况，就是当链表为空时，我们插入结点即要生成一个新的循环有序链表，那么我们可以先处理这个特殊情况，比较简单，就是新建一个结点，然后将next指针指向自己即可。好，下面来看给定的链表不为空的情况，最常见的情况就是要插入的结点值在两个有序结点值[a, b]之间，那么只要满足 a <= insertVal <= b 即可。由于是循环有序的链表，结点值不会一直上升，到某一个结点的时候，是最大值，但是下一个结点就是最小值了，就是题目中的例子，结点4到结点1的时候，就是下降了。那么在这个拐点的时候，插入值insertVal就会有两种特殊的情况，其大于等于最大值，或者小于等于最小值，比如插入值是5，或者0的时候，这两种情况都插入在结点4之后，可以放一起处理。而若其小于最大值，或者大于最小值，就是上面那种一般的情况，不会在这里处理，所以我们只要检测如果属于上面的两种情况之一，就break掉循环，进行插入结点处理即可
Node* insert(Node* head, int insertVal) { if (!head) { head = new Node(insertVal, NULL); head->next = head; return head; } Node *pre = head, *cur = pre->next; while (cur != head) { if (pre->val <= insertVal && cur->val >= insertVal) break; if (pre->val > cur->val && (pre->val <= insertVal || cur->val >= insertVal)) break; pre = cur; cur = cur->next; } pre->next = new Node(insertVal, cur); return head; }
https://segmentfault.com/a/1190000017139433
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;
}1) Linked List is empty:
a) since new_node is the only node in CLL, make a self loop.
new_node->next = new_node;
b) change the head pointer to point to new node.
*head_ref = new_node;
2) New node is to be inserted just before the head node:
(a) Find out the last node using a loop.
while(current->next != *head_ref)
current = current->next;
(b) Change the next of last node.
current->next = new_node;
(c) Change next of new node to point to head.
new_node->next = *head_ref;
(d) change the head pointer to point to new node.
*head_ref = new_node;
3) New node is to be inserted somewhere after the head:
(a) Locate the node after which new node is to be inserted.
while ( current->next!= *head_ref &&
current->next->data data)
{ current = current->next; }
(b) Make next of new_node as next of the located pointer
new_node->next = current->next;
(c) Change the next of the located pointer
current->next = new_node;
void sortedInsert(Node new_node) { Node current = head; // Case 1 of the above algo if (current == null) { new_node.next = new_node; head = new_node; } // Case 2 of the above algo else if (current.data >= new_node.data) { /* If value is smaller than head's value then we need to change next of last node */ while (current.next != head) current = current.next; current.next = new_node; new_node.next = head; head = new_node; } // Case 3 of the above algo else { /* Locate the node before the point of insertion */ while (current.next != head && current.next.data < new_node.data) current = current.next; new_node.next = current.next; current.next = new_node; } }
