报数

#include <bits/stdc++.h>
using namespace std;
struct LinkedList {
    int data;
    LinkedList *fLink;
    LinkedList *bLink;
};
/* 在节点list指向的对象后面插入节点node 并返回节点node */
LinkedList *append_node(LinkedList *list, LinkedList *node) {
    list->bLink = node;
    node->fLink = list;
    return node;
}
/* 在链表中删除节点node 并返回删除node后 此位置应放置的节点 */
LinkedList *remove_node(LinkedList *node) {
    if (node->fLink) {
        node->fLink->bLink = node->bLink;
    }
    if (node->bLink) {
        node->bLink->fLink = node->fLink;
    }
    LinkedList *ret = node->bLink;
    node->fLink = node->bLink = NULL;
    free(node);
    return ret;
}
int main() {
    int n, k;
    /* 构造1~n的环形双向链表 */
    LinkedList *head = (LinkedList *) malloc(sizeof(LinkedList));
    head->data = 1;
    head->fLink = NULL;
    head->bLink = NULL;
    LinkedList *cur = head;
    scanf("%d%d", &n, &k);
    for (int i = 2; i <= n; ++i) {
        cur = append_node(cur, (LinkedList *) malloc(sizeof(LinkedList)));
        cur->data = i;
    }
    cur->bLink = head;
    head->fLink = cur;
    cur = head;
    for (int i = n; i > 1; --i) {
        /* 从编号为1的节点到编号为k的节点 需要移动k-1次 对于环的长度为i的情况 k-1和(k-1)%i等价 */
        int kk = (k - 1) % i;
        while (kk--) cur = cur->bLink;
        cur = remove_node(cur);
    }
    printf("%d\n", cur->data);
    /* 删除最后剩余的1个节点(非必要) */
    remove_node(cur);
    return 0;
}