708. Insert into a Sorted Circular Linked List

O(n) time O(1) space
one pass

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val) {
        val = _val;
        next = NULL;
    }

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if (!head) {
            auto res = new Node(insertVal);
            res->next = res;
            return res;
        }
        auto prev = head, curr = head->next;
        do { // 因为上来如果判断prev != head没法写循环，改成dowhile就可以了
            if (prev->val <= insertVal && insertVal <= curr->val) break;
            if (prev->val > curr->val && (prev->val <= insertVal || insertVal <= curr->val)) break;
            prev = curr;
            curr = prev->next;
        } while (prev != head);
        prev->next = new Node(insertVal, curr);
        return head;
    }
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/
class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if (!head) { // 一定要注意空表！！！
            auto res = new Node(insertVal);
            res->next = res;
            return res;
        }
        auto prev = head, curr = prev->next;
        while (curr != head) { // curr == head说明已经找了一圈了都不符合要求，这是最后一个，只能这个了
            if (prev->val <= insertVal && insertVal <= curr->val) break; // 终止条件1：insertVal恰好在prev和curr之间
            if (prev->val > curr->val && (prev->val <= insertVal || insertVal <= curr->val)) break; // 终止条件2：升序序列，insertVal恰好比最大的数大或者比最小的数小，必须最大的严格大于最小的，否则可能插入错误
            prev = curr;
            curr = prev->next;
        } // 如果都不符合要求，则说明head之前就是应该插入的地方
        prev->next = new Node(insertVal, curr);
        return head;
    }
};

two pass

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/
class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if (!head) {
            auto res = new Node(insertVal);
            res->next = res;
            return res;
        }
        auto curr = head;
        while (curr->next != head && curr->val <= curr->next->val) {
            curr = curr->next;
        }
        auto prev = curr, smallest = prev->next;
        curr = smallest;
        while (curr->val < insertVal) {
            prev = curr;
            curr = prev->next;
            if (curr == smallest) break;
        }
        prev->next = new Node(insertVal, curr);
        return head;
    }
};