708. Insert into a Cyclic Sorted List

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

    public Node() {}

    public Node(int _val,Node _next) {
        val = _val;
        next = _next;
    }
};
*/
/*
Single Pass
Refer: https://leetcode.com/problems/insert-into-a-cyclic-sorted-list/discuss/149374/Java-5ms-One-Pass-and-Two-Pass-Traverse-With-Detailed-Comments-and-Edge-cases!

Time Complexity: O(n)
Space Complexity: O(1)
n = number of nodes in the list
*/
class Solution {
    public Node insert(Node head, int insertVal) {
        // if start is null, create a node pointing to itself and return
        if (head == null) {
            Node node = new Node(insertVal, null);
            node.next = node;
            return node;
        }
        // is start is NOT null, try to insert it into correct position
        Node cur = head;
        while (true) {
            // case 1A: has a tipping point, still climbing
            if (cur.val < cur.next.val && cur.val <= insertVal && insertVal <= cur.next.val) {
                insertAfter(cur, insertVal);
                break;
            // case 1B: has a tipping point, about to return back to min node
            } else if (cur.val > cur.next.val && (cur.val <= insertVal || insertVal <= cur.next.val)) {
                insertAfter(cur, insertVal);
                break;
            // case 2: NO tipping point, all flat
            } else if (cur.next == head) {
                insertAfter(cur, insertVal);
                break;
            }
            // None of the above three cases met, go to next node
            cur = cur.next;
        }
        return head;
    }

    public void insertAfter(Node node, int insertVal) {
        node.next = new Node(insertVal, node.next);
    }
}