有序的环形单指针列表在保持有序的前提下,插入给定新结点x。把列表看成从小到大有序排列,一共有以下这些情况:1. 插入的点在中间,即cur->val <= x && x <= next->val 2. 在末尾next->val < cur->val && cur->val <= x 3. 在开头,next->val < cur->val && x <= next->val。遍历时遇到这三种情况后break并插入。为了防止遍历陷入死循环(如2->2->2),检查cur!=head。
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/*
* @param node: a list node in the list
* @param x: An integer
* @return: the inserted new list node
*/
ListNode * insert(ListNode * head, int x) {
ListNode *cur = head, *res = new ListNode(x), *next = NULL;
if (head == NULL) {
res->next = res;
return res;
}
next = cur->next;
while (cur->next != head) {
if (next->val < cur->val && (cur->val <= x || x <= next->val)) {
break;
}
if (cur->val <= x && x <= next->val) {
break;
}
cur = cur->next;
next = cur->next;
}
cur->next = res;
res->next = next;
return res;
}
};