## C Program to Solve Josephus Problem Using Linked List

``````/*
* C Program to Solve Josephus Problem using Linked List
*/
#include <stdio.h>
#include <stdlib.h>

struct node
{
int num;
struct node *next;
};

void create(struct node **);
void display(struct node *);
int survivor(struct node **, int);

int main()
{
struct node *head = NULL;
int survive, skip;

printf("The persons in circular list are:\n");
printf("Enter the number of persons to be skipped: ");
scanf("%d", &skip);
survive = survivor(&head, skip);
printf("The person to survive is : %d\n", survive);

return 0;
}

int survivor(struct node **head, int k)
{

struct node *p, *q;
int i;

q = p = *head;
while (p->next != p)
{
for (i = 0; i < k - 1; i++)
{
q = p;
p = p->next;
}
q->next = p->next;
printf("%d has been killed.\n", p->num);
free(p);
p = q->next;
}

return (p->num);
}

void create (struct node **head)
{
struct node *temp, *rear;
int a, ch;

do
{
printf("Enter a number: ");
scanf("%d", &a);
temp = (struct node *)malloc(sizeof(struct node));
temp->num = a;
temp->next = NULL;
if (*head == NULL)
{

}
else
{
rear->next = temp;
}
rear = temp;
printf("Do you want to add a number [1/0]? ");
scanf("%d", &ch);
} while (ch != 0);
}

void display(struct node *head)
{
struct node *temp;

printf("%d   ", temp->num);
temp = temp->next;
while (head != temp)
{
printf("%d   ", temp->num);
temp = temp->next;
}
printf("\n");
}
``````