本文共 1113 字，大约阅读时间需要 3 分钟。

来历：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

实际上，上面那么多完全可以用几行话来代替：

1、一群人围在一起坐成环状（如：N） 2、从某个编号开始报数（如：K） 3、数到某个数（如：M）的时候，此人出列，下一个人重新报数 4、一直循环，直到所有人出列 [3] ，约瑟夫环结束 有没有发现，这实际上就和我们小时候玩过的游戏丢手绢基本上是一样的

那么，如何用单链表来实现约瑟夫环尼

第一步：将单链表变成环 第二步：开始循环删除元素，直到最后只剩下一个元素为止（这里面的循环条件要注意）

void Joceph(Node *first, int k){    assert(first);    Node *cur = first;    Node *prev = NULL;    int count = k;    //将单链表变成环    while (cur->next != NULL)    {        cur = cur->next;    }    cur->next = first;    cur = first;    //从头开始    while (cur->next != cur)    {        //因为k如果为3，循环会执行三次，最终删除的结点将会是第四个结点        //所以，循环执行k-1次，就会删除第k个结点        k = count - 1;        while (k--)        {            prev = cur;            cur = cur->next;        }        prev->next = cur->next;        free(cur);        cur = prev->next;    }    printf("%d\n", cur->data);}