n people stand in a circle, numbered 1 to n. Counting starts at person 1, and every k-th person leaves the circle; counting goes on from the person after the one who left. Print the people in the order they leave. The last number printed is the survivor.
Use a circular linked list.
What to build
A circular linked list that people leave one at a time.
Requirements
- Join the last node to the first.
- Count
kpeople each round, then unlink and free the last one counted. - Print the people in the order they leave.
Input
One line with n and k (1 ≤ n ≤ 200, 1 ≤ k ≤ 200).
Output
The n numbers on one line, separated by spaces.
Constraints
1 ≤ n ≤ 200 and 1 ≤ k ≤ 200.
Example
Input:
5 2
Output:
2 4 1 5 3
Why it works
A circle has no end to fall off, so counting simply continues past the last person. Keeping a pointer to the node before makes unlinking a single step.
Examples
5 2
2 4 1 5 3
4 1
1 2 3 4
Hints
Hint 1
Build a circular list 1..n: the last node's next is the first node.
Hint 2
Keep a pointer prev to the node before the one being counted; it starts at the last node.
Hint 3
Each round: move prev k - 1 steps, then remove prev->next, print it and free it.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int value;
struct node *next;
} Node;
int main(void) {
int n, k;
scanf("%d %d", &n, &k);
Node *first = NULL, *last = NULL;
for (int i = 1; i <= n; i++) {
Node *p = malloc(sizeof(Node));
p->value = i;
if (first == NULL) first = p;
else last->next = p;
last = p;
}
last->next = first;
Node *prev = last;
for (int left = n; left > 0; left--) {
for (int s = 1; s < k; s++) prev = prev->next;
Node *out = prev->next;
prev->next = out->next;
if (left < n) printf(" ");
printf("%d", out->value);
free(out);
}
printf("\n");
return 0;
}