/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
//思路
/*
这道题就是要把所有的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插进去。
*/
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
        ListNode* newNode = new ListNode(x);

        if (node == NULL) {
            newNode->next = newNode;
            return newNode;
        }

        ListNode* prev = NULL;
        ListNode* cur = node;

        do {
            prev = cur;
            cur = cur->next;

            if (x >= prev->val && x <= cur->val) {
                break;
            }

            if (prev->val > cur->val && (x <= cur->val || x >= prev->val)) {
                break;
            }
        } while (cur != node);

        prev->next = newNode;
        newNode->next = cur;

        return newNode;
    }
};