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

Have you met this question in a real interview?

Yes

Example

Given a list, and insert a value4:
3->5->1
Return5->1->3->4

we will have the node to travel a round (dummy = node and use node.next == dummy to decide whether we have traveled a round)

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param node a list node in the list
     * @param x an integer
     * @return the inserted new list node
     */
    public ListNode insert(ListNode node, int x) {
        // Write your code here

        ListNode head = new ListNode(x);
        if (node == null) {
            head.next = head;
            return head;
        }

        ListNode dummy = node;
        while (node.next != dummy) {
            if ((x >= node.val && x <= node.next.val) || (node.next.val < node.val && x >= node.val)) {
                break;
            }

            node = node.next;
        }

        ListNode temp = node.next;
        node.next = head;
        head.next = temp;
        return head;

    }
}