Cyclic Sorted List

Problem from : http://programmingpraxis.com/
=====================================================
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
=====================================================

This problem got my attention as I am kinda fond of lists.
I worked out my logic, this way

1) If node passed in is NULL, => no elements so far in list.
create a new node and back point to itself
2) first and last elements of list i.e. highest or lowest (could be equal too)
It should be inserted at the end or beginning (both same as it's cyclic list)
3) Any other element to be inserted in the middle (could be equal to one of the elements)
find prev->elem <= elem_to_insert <= next->elem

Tricky part I find here is, for cases (2) and (3), we might have to get to the starting point of the list. This is because we are given some random node as input, not the head node. So, element we need to insert might just happen go before the input node. So, we start from input node and make a loop through all the nodes until we hit the same input node again.

After going over and going over again to crisp it(;), here is my solution!

=====================================================

<pre class="prettyprint">

typedef struct node_ {
    int x;
    node *next;
} node_t;


node_t* create_node(node_t *node_next,int to_insert) {
    node_new = malloc(sizeof(struct node_));
    if (node_new != NULL) {
        node_new->x = to_insert;
        node_new->next = node_next;
    } else {
         printf("\n Malloc failed. \n");
         exit(0);
    }   
    return node_new;
}

node_t *insert_node(node_t *curr, int i) {
    node_t *node_new=NULL, *prev=NULL,*given_node;
    given_node = curr;
    if (curr == NULL) {
        //empty list
        node_new = create_node(curr,to_insert);
        node_new->next = node_new; //point to itself
    } else { //not an empty list
        do {
            prev = curr;
            curr = curr->next;

            /* insert at beginning or end - highest or lowest */
            if ((prev->x > curr->x)  &&
                 (i >= prev->x || i <= curr->x))
                 break;

            /* insert in between */
            if ( i >= prev->x && i <= curr->x)
                break;
        }  while (curr != given_node);

        node_new = create_node(curr,i);
    }
    return node_new;
}