正文
Leetcode Articles: Insert into a Cyclic Sorted List
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
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.
Solution:
Basically, you would have a loop that traverse the cyclic sorted list and find the point where you insert the value (Let’s assume the value being inserted called
x
). You would only need to consider the following three cases:
1. prev→val ≤ x ≤ current→val:
Insert between prev and current.
2. x is the maximum or minimum value in the list:
- Insert before the head. (ie, the head has the smallest value and its prev→val > head→val.
3. Traverses back to the starting point:
- Insert before the starting point.
It's tricky to think of case 3:
Q: What if the list has only one value?A: Handled by case 3).
Q: What if the list is passed in as NULL?A: Then handle this special case by creating a new node pointing back to itself and return.
Q: What if the list contains all duplicates?A: Then it has been handled by case 3).
public class Solution {
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
this.val = x;
this.next = this;
}
}
public ListNode rotateRight(ListNode start, int x) {
if (start == null) return new ListNode(x);
ListNode cur = start;
while (true) {
if (cur.val < cur.next.val) {//没有到拐点
if (x>=cur.val && x<=cur.next.val) {
insert(cur, x);
break;
}
else cur = cur.next;
}
else if (cur.val > cur.next.val) { //到了拐点
if (x>=cur.val || x<=cur.next.val) {
insert(cur, x);
break;
}
else cur = cur.next;
}
else { //cur.val == cur.next.val
if (cur.next == start) {
insert(cur, x);
break;
}
cur = cur.next;
}
}
return start;
}
public void insert(ListNode cur, int x) {
ListNode node = new ListNode(x);
node.next = cur.next;
cur.next = node;
}
}
