环形单链表的约瑟夫问题

逃离我推掉我的手 2022-07-24 11:03 177阅读 0赞

## 环形单链表的约瑟夫问题 ##

题目：  
约瑟夫环（约瑟夫问题）是一个数学的应用问题：  
已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌只剩一个人。

--------------------

解题思路：  
1、如果链表为空，或者链表节点数为1，return head；  
2、环形链表中循环遍历每个节点，不断转圈，不断让每个节点报数  
3、当报数达到m时，删除当前报数的节点  
4、删除节点后重新连接为环形  
5、待剩余最后一个结点时return结束。

--------------------

链表结点结构定义：

typedef struct Node
    {
        int data;
        struct Node* next;
    }node, *pLinkedList;

算法代码：

Node* josephus(pLinkedList head, int m)
    {
        if (head == NULL || head->next == head)
            return head;
    
        pLinkedList last = head;
    
        //将last设置为head前一个节点
        while (last->next != head)
        {
            last = last->next;
        }
    
        int count = 0;
        while (head != last)
        {
            //报数够m时删除当前节点，即head节点
            if (++count == m)
            {
                last->next = head->next;
                free(head); 
                head = NULL;
                count = 0;//count重新置为0
            }
            else
            {
                last = last->next;
            }
            head = last->next;
        }
    
        return head;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，177人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java环形链表实现约瑟夫环问题

约瑟夫环问题简介环形链表图解思路分析图解： 1.报数分析 2.指针移动，first指针移动

快来打我*/ 2024年04月08日 13:13/ 0 赞/ 89 阅读

相关单向环形链表解决Josephu(约瑟夫)问题

文章目录约瑟夫问题的示意图 1.单向环形链表的构建与遍历思路分析与代码实现代码实现测试添加与展示方法 2.单向环形链表的

╰+哭是因爲堅強的太久メ/ 2023年10月11日 17:16/ 0 赞/ 23 阅读

相关约瑟夫问题经典算法，环形链表的运用

问题背景：据说在很久很久以前，约瑟夫及其部下被逼退到了一个山洞里面，走头无路，大家又不甘投降叛变，于是大家决定一起赴死，他们一起围成了一个圈，然后准备依次报数，当谁的数字

我不是女神ヾ/ 2023年06月18日 04:53/ 0 赞/ 20 阅读

相关链表—约瑟夫问题

单向环形链表应用场景约瑟夫问题：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m 的那个人出列，它的下一位

爱被打了一巴掌/ 2022年12月02日 10:51/ 0 赞/ 205 阅读

相关环形单链表解决约瑟夫环问题

package com.example.datastructrue.linkedlist; public class JosephuDemo {

红太狼/ 2022年09月07日 14:56/ 0 赞/ 208 阅读

相关环形单链表的约瑟夫问题

环形单链表的约瑟夫问题题目：约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数

逃离我推掉我的手/ 2022年07月24日 11:03/ 0 赞/ 178 阅读

相关环形链表，约瑟夫问题，（7）

一个经典的环形链表问题，有1,2，3，，，，n这些数字排成一个圆圈，从1开始每次删除第m个数字，求出这个圆圈中最后的数字。当然也可以说先从数字k开始，数到m删除这个数字，然后就

àì夳堔傛蜴生んèń/ 2022年06月09日 11:22/ 0 赞/ 229 阅读

相关 Java——环形单链表的约瑟夫问题

【题目】　　41个人排成一个圆圈，由第1个人开始报数，报数到3的人就自杀，然后再由下一个人重新报1，报数到3的人再自杀，这样依次下去，知道剩下最后一个人时，那个人可以自由

我不是女神ヾ/ 2022年06月05日 06:11/ 0 赞/ 190 阅读

相关环形单链表的增、删，查（约瑟夫问题）

创建数据结构编号、next。私有形式然后用构造器初始化，用getset进行封装，创建环形单链表初始化头头不动 package com.linkedlist;

ゝ一纸荒年。/ 2021年11月17日 05:20/ 0 赞/ 279 阅读

相关 go 环形单向链表实现约瑟夫问题

一 Josephu 问题 Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1开始报数，数到 m 的那个人出

清疚/ 2021年07月24日 12:28/ 0 赞/ 450 阅读