Josephus problem using a linked list using malloc

Question

I'm planning to solve the Josephus problem in C using a linked list, but it doesn't work. I've tried multiple ways to do it, so I'm confused.

#include "stdlib.h"
#include "stdio.h"

struct Node {
    int num;
    struct Node *Next;
};

typedef struct Node *PtrToNode;

int main() {
    int n, m, i;
    PtrToNode p, q;

    printf("Please input n, m\n");
    scanf("%d %d", &n, &m);

    p = (PtrToNode)malloc(sizeof(struct Node));
    p->num = 1;
    p->Next = p;

    for (i = 2; i <= n; i++) {
        q = (PtrToNode)malloc(sizeof(struct Node));
        q->num = i;
        q->Next = p;
        p->Next = q;
        p = q;
    }

    while (q->Next != q) {
        for (i = 1; i <= m; i++)
            p = q->Next;
        q = p;
        printf("%d, ", q->num);
        p->Next = NULL;
        free(q);
    }
    printf("%d\n", p->num);
    free(p);
    //system("pause");
    return 0;
}

I kind of understand the struct function and the typedef, so I guess I don't have any problem there (?). I'm guessing I made a mistake in the main function.

Answer 1

Some of the issues:

• The following assignments in the first loop create a cycle that always has length 2:

  q->Next = p;
  p->Next = q;
  

  The intention was to link back to the first node, but you don't have a reference to the first node anymore, only the previous (p). So introduce another variable that will not move: head, and then link back with q->next=head. And actually you can do that after the loop, just for the last node that was added.

• In the next loop, inside the for loop, the following will do the same thing in each iteration:

  p = q->Next;
  

  Since q is not moving, this just results in the same value being assigned to p in each iteration. It would make more sense to do q = q->Next

• Your code does not properly detach the node that is going to be deleted. It merely ends the list there:

  p->Next = NULL;
  

  This does not take into account that there is a node preceding p that is still referencing p. It is actually that preceding node that needs to be rewired. So you will actually want the preceding loop to stop one step earlier, so you have the reference to the preceding node q, and then do:

  p = q->Next; // p will be deleted
  q->Next = p->Next; // Rewiring around p
  

Here is the corrected main:

int main() {
    int n, m, i;
    PtrToNode head, p, q;

    printf("Please input n, m\n");
    scanf("%d %d", &n, &m);
    printf("Input was n=%d, m=%d\n", n, m);

    head = (PtrToNode)malloc(sizeof(struct Node));
    head->num = 1;

    p = head;
    for (i = 2; i <= n; i++) {
        q = (PtrToNode)malloc(sizeof(struct Node));
        q->num = i;
        p->Next = q;
        p = q;
    }
    p->Next = head;

    while (q->Next != q) {
        for (i = 1; i < m; i++)
            q = q->Next;
        p = q->Next;
        printf("%d, ", p->num);
        q->Next = p->Next;
        free(p);
    }
    printf("%d\n", q->num);
    free(q);
    return 0;
}