• 【牛客网刷题(数据结构)】:环形链表的约瑟夫问题


    在这里插入图片描述
    描述
    编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数,报到 m 的人离开。
    下一个人继续从 1 开始报数。
    n-1 轮结束以后,只剩下一个人,问最后留下的这个人编号是多少?
    O(n)
    示例1
    环形链表的约瑟夫问题是一个经典的问题,它的描述如下:有n个人围成一圈,从第一个人开始报数,报到m的人出圈,剩下的人继续从1开始报数,直到剩下最后一个人。现在给定n和m,求最后剩下的人的编号
    这个问题可以使用环形链表来解决。具体来说,我们可以先构建一个包含n个节点的环形链表,然后从第一个节点开始遍历链表,每次遍历m个节点,将第m个节点从链表中删除。重复这个过程直到链表中只剩下一个节点为止,这个节点就是最后剩下的节点
    输入:
    5,2
    返回值:
    3
    说明:
    开始5个人 1,2,3,4,5 ,从1开始报数,1->1,2->2编号为2的人离开
    1,3,4,5,从3开始报数,3->1,4->2编号为4的人离开
    1,3,5,从5开始报数,5->1,1->2编号为1的人离开
    3,5,从3开始报数,3->1,5->2编号为5的人离开
    最后留下人的编号是3
    示例2
    输入:
    1,1
    复制
    返回值:
    1
    关于环形链表的约瑟夫问题,具体思路如下:
    首先创建一个环形链表,链表中每个节点代表一个人,节点编号从1开始递增。
    然后从第一个节点开始报数,每报到第m个人就将该节点从链表中删除。
    删除节点后,从下一个节点重新开始报数,重复上述步骤,直到只剩下一个节点为止。
    下面是C++代码实现:

    #include 
    using namespace std;
    
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    
    int josephus(int n, int m) {
        ListNode* head = new ListNode(1);
        ListNode* cur = head;
        for (int i = 2; i <= n; i++) {
            cur->next = new ListNode(i);
            cur = cur->next;
        }
        cur->next = head; // 将链表首尾相连
    
        while (cur->next != cur) { // 只剩下一个节点时结束循环
            for (int i = 1; i < m; i++) {
                cur = cur->next;
            }
            ListNode* tmp = cur->next;
            cur->next = tmp->next;
            delete tmp;
        }
        int ans = cur->val;
        delete cur;
        return ans;
    }
    
    int main() {
        int n, m;
        cin >> n >> m;
        cout << josephus(n, m) << endl;
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    C语言代码实现

    #include 
    #include 
    
    // 定义链表节点结构体
    typedef struct Node {
        int num;            // 节点编号
        struct Node *next;  // 指向下一个节点的指针
    } Node;
    
    // 创建环形链表
    Node *createList(int n) {
        Node *head = NULL, *tail = NULL;
        for (int i = 1; i <= n; i++) {
            Node *p = (Node *)malloc(sizeof(Node));
            p->num = i;
            if (head == NULL) {
                head = p;
            } else {
                tail->next = p;
            }
            tail = p;
        }
        tail->next = head;  // 将尾节点指向头节点,形成环形链表
        return head;
    }
    
    // 约瑟夫问题求解
    void josephus(Node *head, int m) {
        Node *p = head, *prev = NULL;
        while (p->next != p) {  // 只剩下一个节点时结束循环
            for (int i = 1; i < m; i++) {
                prev = p;
                p = p->next;
            }
            prev->next = p->next;  // 删除节点
            printf("%d ", p->num);
            free(p);
            p = prev->next;  // 从下一个节点重新开始报数
        }
        printf("%d\n", p->num);
        free(p);
    }
    
    int main() {
        int n, m;
        printf("请输入总人数n和报数m:");
        scanf("%d%d", &n, &m);
        Node *head = createList(n);
        josephus(head, m);
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
  • 相关阅读:
    java虚拟机垃圾回收基本概念
    「PAT乙级真题解析」Basic Level 1091 N-自守数 (问题分析+完整步骤+伪代码描述+提交通过代码)
    moment()获取时间
    ChatGPT和文心一言分析茅台与瑞幸的联名盛宴:酱香拿铁背后的商业布局
    [附源码]计算机毕业设计基于SpringBoot的在线作业批改系统
    maven升级版本后报错:Blocked mirror for repositories
    [Java]注释——注释真的需要么?
    服务领域模型
    【Java从入门到精通】Java异常处理
    linux 文件意外退出后,利用swp文件恢复未保存的版本。
  • 原文地址:https://blog.csdn.net/fjj2397194209/article/details/133828609