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. (increasing sorted)

We need to consider the following three cases:

1. pre->val <=x<=current->val:

insert between prev and current.

2. x is the maximum or minimum value in the list:

Insert before the head.

3. Traverses back to the starting point:

Insert before the starting point.

// aNode是引用，当aNode为空时，返回结点的指针

void insert(Node*& aNode, int x)

{

    if (!aNode)

    {

        aNode = new Node(x);

        aNode->next = aNode;

        return;

    }

    Node* p = aNode;

    Node* prev = NULL;

    do

    {

        prev = p;

        p = p->next;

        if (x <= p->data && x >= prev->data)

            break;

        if ((prev->data > p->data) && (x < p->data || x > pre->data))

            break;

    } while (p != aNode);

    Node* newNode = new Node(x);

    newNode->next = p;

    prev->next = newNode;

}

http://leetcode.com/2011/08/insert-into-a-cyclic-sorted-list.html