LC: Insert into a Sorted Circular Linked List - spiralgo/algorithms GitHub Wiki

Insert into a Sorted Circular Linked List

The Essence:

Here, it's best to think about what might occur when a value is being inserted into such a list:

• It could be inserted between values. (5 will naturally be inserted after 4 and before 6.)
• It could be inserted at the end of the list. At the end of the list, the next value is smaller than the previous one. A node would be inserted here if and only if it succeeds the largest value or precedes the smallest value.

The algorithm follows from these simple observations.

Details:

For this, 2 node pointers (prev and next) can be used to find the place to insert. The list can be traversed until one of the conditions above are met.

The implementation can be found here: https://github.com/spiralgo/algorithms/blob/master/src/main/java/algorithms/curated170/medium/InsertIntoASortedCircularLinkedList.java