Lintcode - Insert into a Cyclic Sorted List

Given a node from a cyclic linked list which has been sorted, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be any single node in the list. Return the inserted new node.

Notice

3->5->1is a cyclic list, so3is next node of1.
3->5->1is same with5->1->3

Analysis: this is an "easy" question but lots of boundary conditions need to be considered. For example,

10->10->9->10, 9
10->10->9->9->10, 9
1->2->3->4, 5
2->3>4->5, 1

Also this is a good example of when to use do-> while loop instead of while loop.

Solution

public ListNode insert(ListNode node, int x) {
    ListNode newNode = new ListNode(x);
    if (node == null) {
        newNode.next = newNode;
        return newNode;
    }

    ListNode benchMark = node;
    ListNode insertPoint = null;
    ListNode maxNode = null;

    do {
        if (maxNode == null || node.val > maxNode.val) {
            maxNode = node;
        }

        if (node.val <= x) {
            if (insertPoint == null) {
                insertPoint = node;
            } else {
                if (node.val >= insertPoint.val) {
                    insertPoint = node;
                }
            }
        }
        node = node.next;
    } while (node != benchMark);

    if (insertPoint == null) {
        insertPoint = maxNode;
    }

    ListNode temp = insertPoint.next;
    insertPoint.next = newNode;
    newNode.next = temp;
    return newNode;
}