单链表实现约瑟夫环

悠悠 2022-05-12 09:06 226阅读 0赞

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

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

![这里写图片描述][70]

那么，如何用单链表来实现约瑟夫环尼  
第一步：将单链表变成环  
第二步：开始循环删除元素，直到最后只剩下一个元素为止（这里面的循环条件要注意）

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);
    }

[70]: /images/20220512/f3a292341d5c462ab0a45859e0503ce6.png