环形链表的约瑟夫问题

题目描述

据说著名犹太历史学家 Josephus 有过以下故事：在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一种自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，报数到 3 的人就自杀，然后再由下一个人重新报 1，报数到 3 的人再自杀，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表得出最终存活的人的编号。

输入描述：

一行两个整数 n 和 m， n 表示环形链表的长度， m 表示每次报数到 m 就自杀。

输出描述：

输出最后存活下来的人编号(编号从1开始到n)

示例1

输入

5 2

输出

3

备注：

1 ≤ n , m ≤ 10000 1 leq n,m leq 10000 1≤n,m≤10000

题解：

题目要求用单向环形链表，那就用呗。。。循环遍历 n-1 次，每次数到第 m 个人就杀掉，模拟就行，就是时间复杂度有点高。。。

代码：

#include <cstdio>

using namespace std;

struct list_node{
          
   
    int val;
    struct list_node * next;
};

list_node * input_list(int n)
{
          
   
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    for (int i = 1; i <= n; ++i) {
          
   
        if (i == 1) {
          
   
            cur_pnode->val = i;
            cur_pnode->next = NULL;
        }
        else {
          
   
            list_node * new_pnode = new list_node();
            new_pnode->val = i;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    cur_pnode->next = phead;
    return phead;
}

int josephusKill(list_node*& head, int m) {
          
   
    if (head->next == head || m < 1) return head->val;
    list_node *p = head, *pre = NULL;
    while (p->next != p) {
          
   
        for (int i = 1; i < m; ++i) {
          
   
            pre = p;
            p = p->next;
        }
        pre->next = p->next;
        p = pre->next;
    }
    return p->val;
}

int main(void) {
          
   
    int n, m;
    scanf("%d%d", &n, &m);
    list_node * phead = input_list(n);
    printf("%d
", josephusKill(phead, m));
    return 0;
}