Linked list issue - loop iterates over wrong nodes

Question

If you are not familiar with Josephus problem:

There are N soldiers standing in a circle.They all get executed starting by 1 and moving by M.In the end only one of them stands alive. the code below ask for N and M and generated the last player standing.

#include <stdio.h>
#include <stdlib.h>
int main()
{
int N, M;
struct node { int player_id; struct node *next; }
struct node *p, *q;
int i, count;

printf("Enter N (number of players): "); scanf("%d", &N);
printf("Enter M (every M-th payer gets eliminated): "); scanf("%d", &M);

// Create circular linked list containing all the players:

p = q = malloc(sizeof(struct node));

p->player_id = 1;

for (i = 2; i <= N; ++i) {
    p->next = malloc(sizeof(struct node));
    p = p->next;
    p->player_id = i;
}  

p->next = q;// Close the circular linkedlist by having the last node point to the 1st  

// Eliminate every M-th player as long as more than one player remains:

for (count = N; count > 1; --count) {
   for (i = 0; i < M - 1; ++i)
      p = p->next;

   p->next = p->next->next;  // Remove the eiminated player from the circular linkedl
}

printf("Last player left standing is %d\n.", p->player_id);

return 0;
}

Lets say N=17;M=7 the output should be 13 the program above generates 2 (what happens? well it starts the counting from M not from 1 so instead of 1,8,15...... it elimintates 7,14......) This is where i need your help (as linked lists are still a difficult concept for me). How to modify this one?

Answer 1

You have placed the node removal line in the wrong place.

for (count = N; count > 1; --count) {
   for (i = 0; i < M - 1; ++i)
      p = p->next;

   p->next = p->next->next;
}

You placed this line after the loop that count M nodes from the beginning so it always start with removal of (M+1)th node. You should move it before it so that it starts from the first node.

for (count = N; count > 1; --count) {
   p->next = p->next->next;
            for (i = 0; i < M - 1; ++i) p = p->next;

}

Is this what You're looking for?