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

代码未检测

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
        // 在是空的情况，一个node也要首尾相连
        if (node == null)
        {
            ListNode newNode = new ListNode(x);
            newNode.next = newNode;
            return newNode;
        }

        ListNode curr = node;

        while (curr.next != null && curr.next != node)
        {
            if (curr.val <= x && curr.next.val > x)
            {
                break;
            }
            curr = curr.next;
        }

        ListNode temp = curr.next;
        curr.next = new ListNode(x);
        curr.next.next = temp;

        return curr.next;  // both node.next and curr.next work here as it is cycle list
    }
}