C++实现约瑟夫环的循环单链表

C++实现约瑟夫环的循环单链表

1. 算法说明

约瑟夫问题是著名的一种编程问题。一个古老的故事讲述了约瑟夫和他的40个朋友被罗马军队包围在一个洞穴里。他们决定自杀，并排成一个圆圈，从某个位置开始，依据一个固定的规则进行自杀。每一次自杀后，从那个位置开始，依照规则再次自杀，直至只剩下一个人仍然活着。问题就是求这个人的序号。

这个问题可以通过循环单链表来实现。我们可以在链表中存储所有的人，并按照一定的规则进行删除，直到只剩下一个人。

2. 实现步骤

2.1 定义节点

定义一个循环链表节点结构体，包含一个数据域和一个指向下一个节点的指针域。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

2.2 构建链表

根据题目要求，构建一个循环链表，并且每个节点的编号从1开始，一直到n。可以使用一个for循环来构建链表，最后将尾节点指向头结点，形成一个环。

ListNode* createList(int n) {
    if(n <= 0) return NULL;

    ListNode *head = new ListNode(1);
    ListNode *cur = head;

    for(int i = 2; i <= n; ++i) {
        ListNode *node = new ListNode(i);
        cur->next = node;
        cur = node;
    }
    cur->next = head;

    return head;
}

2.3 实现删除操作

根据题目规则，每m个节点进行一次删除操作。我们可以使用两个指针变量，一个指向要删除节点的前一个节点，一个指向要删除节点的后一个节点，然后改变指针指向，删除该节点。

具体实现如下：

int josephus(int n, int m) {
    ListNode *head = createList(n);

    ListNode *prev = head;
    ListNode *cur = head;

    // 找到最后一个节点
    while(cur->next != head) cur = cur->next;

    // 模拟删除过程
    while(cur != prev) {
        for(int i = 1; i < m; ++i) {
            prev = cur;
            cur = cur->next;
        }
        prev->next = cur->next;
        delete cur;
        cur = prev->next;
    }

    int res = cur->val;
    delete cur;

    return res;
}

3. 两个示例

3.1 例子1

输入：n=5, m=3

输出：3

解释：第一次删除2，剩下1、3、4、5；第二次删除5，剩下1、3、4；第三次删除1，剩下3、4；第四次删除4，最后剩下3。

3.2 例子2

输入：n=10, m=7

输出：8

解释：第一次删除7，剩下1、2、3、4、5、6、8、9、10；第二次删除4，剩下1、2、3、5、6、8、9、10；第三次删除2，剩下1、3、5、6、8、9、10；第四次删除10，剩下1、3、5、6、8、9；第五次删除6，剩下1、3、5、8、9；第六次删除3，剩下1、5、8、9；第七次删除9，最后剩下1、5、8。