Josephus problem

Question: Write a function to delete every k^th node from circular linked list until only one node is left.

This has a story associated with it.

Flavius Josephus was Jewish Historian from 1st century. He and 40 other soldiers were trapped in a cave by Romans. They decided to kill themselves rather than surrendering to Romans. Their method was like this.

All the soldiers will stand in a circle and every k^th soldier will be shot dead. Josephus said to have calculated the starting point so that he would remain alive.

So we have similar problem at hand. We delete every kth node in a circular list. Eventually only one node will be left.
e.g.

Let us say this is our list

And we are deleting every third node. 

We will delete 30. Then we delete 60. Next we delete 10. Next it will be 50. Next to be deleted is 20. Next 80. This continues.

Implementation 

We can count k-1 nodes and delete next node. This can be repeated in  a loop. What must be the terminating condition? When do we know there is only one node left?

When node->next = node. That will be our condition for the loop.

We shall write the function now.

NODEPTR delete_nodes(NODEPTR head,int k)
{
    NODEPTR temp = head;
    NODEPTR prevnode = NULL;
    while(temp->next !=temp) 
    {
           int i; 
           for(i=1;i<k;i++)
           {
             prevnode = temp;
      temp = temp->next;
           }
           if(prevnode!=NULL)
            {
        printf("Deleting the node %d\n",temp->n);
        prevnode->next = prevnode->next->next;
               free(temp);
            }
            temp = prevnode->next;
      }
      return temp;
} 

Here is the complete program  

#include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  
 
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 

 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(head==NULL)
      {
 newnode->next = newnode;
        return newnode;
      }
    while(temp->next !=head)
 temp = temp->next;
    temp->next = newnode;
    newnode->next = head;
    return head;  
 } 
 
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head; 
   if(head==NULL)
 return;
   do  
   {  
     printf("%d---->",temp->n);  
     temp = temp->next;  
   } while(temp!=head);
   printf("\n");
 }   
NODEPTR delete_nodes(NODEPTR head,int k)
{
    NODEPTR temp = head;
    NODEPTR prevnode = NULL;
    while(temp->next !=temp) 
    {
           int i; 
           for(i=1;i<k;i++)
           {
             prevnode = temp;
      temp = temp->next;
           }
           if(prevnode!=NULL)
            {
        printf("Deleting the node %d\n",temp->n);
        prevnode->next = prevnode->next->next;
               free(temp);
            }
            temp = prevnode->next;
      }
      return temp;
} 

 int main()  
 {  
     NODEPTR head; 
     int numnodes,i;  
     //initialize head  
     head =  NULL;  
     printf("Number of nodes = ");  
     scanf("%d",&numnodes);  
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head = append_node(head,newnode);      
     }  
     printf("The linked list now is ");  
     display_nodes(head);   
     printf("k=");
     scanf("%d",&i);
     head = delete_nodes(head,i);
     printf("The node remaining is %d\n",head->n);
 }