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->1is a cyclic list, so3is next node of1.
3->5->1is same with5->1->3

Have you met this question in a real interview?

Yes

Example

Given a list, and insert a value4:
3->5->1
Return5->1->3->4

/**
 * 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* node, int x) {
        // Write your code here
        if (node == NULL) {
            node = new ListNode(x);
            node->next = node;
            return node;
        }
        ListNode *prev = node, *cur = node->next;
        do {
            if (prev->val <= x && x <= cur->val) {
                break;
            }
            if (prev->val > cur->val && (x > prev->val || x < cur->val)) {
                break;
            }
            prev = cur;
            cur = cur->next;
        } while (cur != node->next);

        ListNode* newNode = new ListNode(x);
        newNode->next = cur;
        prev->next = newNode;
        return newNode;
    }
};