708. Insert Into A Sorted Circular Linked List

/**

 * 708. Insert into a Sorted Circular Linked List

 * Given a node from a Circular Linked List which is sorted in ascending order,

 * write a function to insert a value insertVal into the list such that it remains a sorted circular list.

 * The given node can be a reference to any single node in the list, and may not be necessarily the smallest value in the circular list.

 * If there are multiple suitable places for insertion, you may choose any place to insert the new value.

 * After the insertion, the circular list should remain sorted.

 * If the list is empty (i.e., given node is null), you should create a new single circular list and

 * return the reference to that single node. Otherwise, you should return the original given node.

 * This problem is not as simple as it seems! Basically the list is circular and it has a turning point

 * where next value is less than prior. The question in leet code doesnt stress the notion of a turning point.

 * Best to ask interviewer of expected scenarios in test data and write out the test cases before solving a problem

 * such as this.

*/

See here the code at github: https://github.com/zcoderz/leetcode/blob/main/src/main/java/linked_list/InsertIntoASortedCircularLinkedList.java

Observation: The data in the list is sorted but since the list has the end connected to start there is a turning point which has to be accounted for. Logic is straightforward, you iterate from left to right list until you reach the head. If you find the value being inserted between prior and next nodes, you found the point. Otherwise, if next is less than prior, this is the turning point and conditions around it need to be handled specifically where:

1. If value being inserted is greater than prior, need to insert here
2. If value being inserted is less than next, need to insert here

Here is the code:

public ListNode insert(ListNode head, int insertVal) {
    if (head == null) {
        ListNode ListNode = new ListNode(insertVal);
        ListNode.next = ListNode;
        return ListNode;
    } else {
        ListNode prior = head;
        ListNode curr = head.next;
        while (curr != head ) {
            if (prior.val <= insertVal && curr.val >= insertVal) {
                //this checks for a simple case where new val is greater than prior but less
                //the current
                break;
            }
            // this condition checks for whether this is the turning point in the list
            if (curr.val < prior.val
            // if turning point and insert value is greater than previous or less than curr
            // the data needs to be inserted here
                    && (insertVal >= prior.val || (insertVal <= curr.val))) {
                break;
            }
            prior = curr;
            curr = curr.next;
        }
        insert(prior, curr, insertVal);
        return head;
    }
}

public void insert(ListNode endListNode, ListNode curr, int insertVal) {
    ListNode ListNode = new ListNode(insertVal);
    endListNode.next = ListNode;
    ListNode.next = curr;
}