Here is my solution for the Josephus Problem (of user inputted sized circle and "magic" number) using a circularly linked list.
Any suggestions on what I could have, or should have, done differently for better efficiency or best practices?
#include <stdio.h> #include <stdlib.h> typedef struct node{ unsigned childNum; struct node* next; }node; unsigned findSolution(unsigned size, unsigned n){ node* firstChild = (node*)malloc(sizeof(node)); node* lastChild = (node*)malloc(sizeof(node)); node* currentChild = (node*)malloc(sizeof(node)); node* trailNode = (node*)malloc(sizeof(node)); node* p; /* used to delete node */ firstChild->childNum = 0; /* if the size of the list to be created is only 1 child, return as the solution */ if(size == 1) return size; /* create the circlularly linked list of size - 1 */ for(unsigned i = 1; i < size; i++){ node* nextChild = (node*)malloc(sizeof(node)); nextChild->childNum = i; nextChild->next = NULL; if(firstChild->childNum < 1){ firstChild = nextChild; lastChild = nextChild; }else{ lastChild->next = nextChild; lastChild = nextChild; } } /* create the last node */ node* nextChild = (node*)malloc(sizeof(node)); nextChild->childNum = size; lastChild->next = nextChild; lastChild = nextChild; lastChild->next = firstChild; /* iterate the list and delete the nth node until currentChild points to itself */ currentChild = firstChild; while(currentChild != NULL && currentChild->next != currentChild){ if(n > 1){ for(unsigned i = 1; i < n; i++){ trailNode = currentChild; currentChild = currentChild->next; } /* delete this child */ trailNode->next = trailNode->next->next; p = currentChild; currentChild = currentChild->next; free(p); }else{ /* n == 1, remove every child */ p = currentChild; /* if the next child is the last child, point it to itself to exit loop */ if(currentChild->next = lastChild){ lastChild->next = lastChild; } currentChild = currentChild->next; free(p); } } /* only 1 node remaining -- this is the solution */ return currentChild->childNum; } int main(void){ unsigned size = 0; unsigned n = 0; do{ printf_s("How many children are in the circle -- must be > 0: "); scanf_s("%u", &size); printf_s("Remove every nth child -- value for n must be > 0: "); scanf_s("%u", &n); printf_s("\n\n"); }while(size < 1 || n < 1); printf_s("Computing the answer..."); printf_s("\n\n\nChild number %li is the winner.", findSolution(size, n)); for(;;); return 0; }