首页 > 试题广场 >

环形链表的约瑟夫问题

[编程题]环形链表的约瑟夫问题
  • 热度指数：24799 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

数据范围： 
进阶：空间复杂度 ，时间复杂度
示例1

输入

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
算法知识视频讲解
添加回答
C
夜雨潇湘人断肠头像 夜雨潇湘人断肠
typedef struct node
{
    int val;
    struct node* next;
}node;

node* buynode(int x)
{
    node* tmp = (node*)malloc(sizeof(node));
    tmp->next = NULL;
    tmp->val = x;
    return tmp;
}

int ysf(int n, int m) {
    node* tmp = NULL;
    node* head = NULL;
    for (int i = 1; i <= n; i++)
    {
        node* cur = buynode(i);
        if (tmp == NULL)
        {
            tmp = cur;
            head = cur;
        }
        else
        {
            tmp->next = cur;
            tmp = cur;
        }
    }
    tmp->next = head;
    int count = 1;
    while (head->next != head)
    {
        node* prev = head;
        head = head->next;
        count++;
        if (count == m)
        {
            prev->next = head->next;
            count = 1;
            head = prev->next;
        }
    }
    return head->val;
}
发表于 2024-08-30 11:43:00 回复(1)
C
__Forever__头像 __Forever__ 
struct ListNode* BuyNode(int x)
{
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    if(node == NULL)
    {
        exit(1);
    }
    node->val = x;
    node->next = NULL;

    return node;    
}
//创建循环链表
struct ListNode* createCircle(int n)
{
    struct ListNode* phead, *ptail;
    phead = ptail = BuyNode(1);
    //创建链表
    for(int i = 2; i <= n; i++)
    {
        ptail->next = BuyNode(i);
        ptail = ptail->next;
    } 
    //尾节点连接头节点
    ptail->next = phead;

    return ptail;
}

int ysf(int n, int m ) {
    // write code here
    //创建循环链表
    struct ListNode* prev = createCircle(n);
    struct ListNode* pcur = prev->next;
    int count = 1;  //count需要从一开始数
    //遍历链表
    while(prev->next != prev)
    {
        if(count == m)
        {
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
            count=1;
        }
        else {
        prev = pcur;
        pcur = pcur->next;
        count++;
        }
    }
    //释放申请的节点空间
    int ret = pcur->val;
    free(pcur);
    pcur = NULL;
    return ret;
    }

发表于 2024-05-25 23:04:52 回复(0)
C
区欠阳头像 区欠阳 
 typedef struct ListNode ListNode;
 // 创建节点
 ListNode* ListBuy(int n)
 {
    ListNode* mode = (ListNode*)malloc(sizeof(ListNode));
    if(mode == NULL)
    {
        exit(1);
    }
    mode->val = n;
    mode->next = NULL;
    return mode;
 }
 // 创建环形链表
 ListNode* CreatCircle(int n)
 {
    // 创建头节点
    ListNode* phead = ListBuy(1);
    // 创建尾节点
    ListNode* ptail = phead;
    for(int i =2; i<=n; i++){
        ptail->next=ListBuy(i);
        ptail=ptail->next;
    }
    // 首尾相连
    ptail->next=phead;

    return ptail;
 }
int ysf(int n, int m ) {
    // write code here
    // 创建环形链表
    ListNode* prev = CreatCircle(n);
    ListNode* pcur = prev->next;
    // 计数
    int count = 1;
    while(prev->next != prev)
    {
        if(count == m)
        {
            // 删除节点
            prev->next=pcur->next;
            free(pcur);
            pcur=prev->next;
            count=1;
        }
        else {
            prev=pcur;
            pcur=pcur->next;
            count++;
        }
    }
    return pcur->val;
}

发表于 2024-04-24 19:54:00 回复(0)
C
温柔的卡尔被发好人卡头像 温柔的卡尔被发好人卡 
typedef struct ListNode LN;

struct ListNode* creatNode(int n)
{
    LN* newNode=(LN*)malloc(sizeof(LN));
    newNode->val=n;
    newNode->next=NULL;
    return newNode;
}

LN* creatCircle(int n)
{
    LN*phead=creatNode(1);//创建第一个节点
    LN*pcur=phead;
    int i=2;
    LN*newNode;
    while(i<=n)
    {
        newNode=creatNode(i++);
        pcur->next=newNode;
        pcur=pcur->next;
        //newNode->next=NULL;
    }
    pcur->next=phead;
    return phead;
}

int ysf(int n, int m ) {
    // write code here
    int count=0;//报数的序号
    int peopleCount=n;
    LN*head=creatCircle(n);//创建环形链表
    LN*pcur=head;
    LN*prev=head;
    while(prev->next->val!=1)//找到尾节点
    {
        prev=prev->next;
    }
    while(1)
    {
        count++;
        if(count==m)//报到m删除节点
        {
            if(peopleCount==2)
            {
                return prev->val;
            } 
            prev->next=pcur->next;
            count=0;
            peopleCount--;
            pcur=pcur->next;
        }
        else 
        {
            pcur=pcur->next;
            prev=prev->next;
        }
        
    }
}

发表于 2024-04-22 17:22:18 回复(0)
C
牛客642523979号头像 牛客642523979号
typedef  struct ListNode ListNode;
 ListNode*buynode(int x)
 {
        ListNode* newnode=(ListNode*)malloc(sizeof(ListNode));
        newnode->val=x;
        newnode->next=NULL;
        return newnode;
 }
ListNode*createlist(int n)
{
    ListNode*phead=buynode(1);
    ListNode*ptail=phead;
    for(int i=2;i<=n;i++)
    {
        ptail->next=buynode(i);
        ptail=ptail->next;
    }
    ptail->next=phead;
    return phead;
 }
int ysf(int n, int m ) {
    // write code here
    ListNode*head=createlist(n);
    int count =1;
    ListNode*pcur=head;
    ListNode*prev=  NULL;
    while(pcur->next!=pcur)
    {
        if(count==m)
        {
        prev->next=pcur->next;
        free(pcur);
        pcur=prev->next;
        count=1;
        }
        else{
            prev=pcur;
            pcur=pcur->next;
            count++;
        }
    }
    return pcur->val;
}
编辑于 2024-03-10 11:18:56 回复(0)
C
牛客995898168号头像 牛客995898168号 
#include <stdlib.h>
typedef struct ListNode ListNode ;
//创建节点
ListNode* CreatNode(int x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));

    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}
//创建链表
ListNode* CreatList(int n)
{
    //先创建头节点
    ListNode* head = CreatNode(1);
    ListNode* ptail = head;
    //循环创建剩余节点，连接至已有节点后
    for (int i=2; i<=n; i++) {
        ListNode* newnode = CreatNode(i);
        ptail->next = newnode;
        //尾节点后移
        ptail = ptail->next;
    }
    //将链表连接成环
    ptail->next = head;
    //return head;
    return ptail; //为防止prev->next为空
}

int ysf(int n, int m ) {
    //创建循环链表
    ListNode* prev = CreatList(n);
    ListNode* pcur = prev->next;
    //ListNode* prev = NULL;
    int count = 1;
    //若节点个数大于1，继续执行删除
    while(pcur->next != pcur)
    {
        //逢m就删除
        if(count == m)
        {
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
            //重新再喊
            count = 1;
        }
        else 
        {
            //不是m，继续喊
            prev = pcur;
            pcur = pcur->next;
            count++;
        }
    }
    return pcur->val;
}

发表于 2024-01-24 16:13:10 回复(0)
C
1188_头像 1188_
求大佬看看这个为什么不行
#include<stdio.h>
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    int a[10000]={0};
    for(int i=1;i<=n;i++)
    {
        a[i]=i;
    }
    int count=0;
    for(int i=1;;i++)
    {
        int k=0;
        if(a[i]!=-1&&a[i]!=0)
        {
            count++;
        }
        if(a[i]==0)
        {
            i=1;
            continue;
        }
        if(count==m)
        {
            printf("%d ",a[i]);
            a[i]=-1;
            count=0;
        }
        for(int j=1;j<=n;j++)
        {
            if(a[j]!=-1)
            {
                k++;
            }
        }
        if(k==0)
        {
            break;
        }
    }
}
发表于 2023-03-16 22:37:41 回复(0)
C
木鱼脑壳儿头像 木鱼脑壳儿 
int ysf(int n, int m ) {
    // write code here
    int s = 0;
    for (int i = 2; i <= n; ++i)
        s = (s + m) % i;
    return s+1;
}

b站评论看到的，拿过来一粘贴就过了。
发表于 2022-07-16 17:23:04 回复(0)
C
牛客830308422号头像 牛客830308422号 
/**
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
int ysf(int n, int m ) {
    // write code here
    struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *p = head;
    head->val = 1;
    for (int i = 2; i <= n; i++) {
        struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
        p->next = node;
        p = node;
        p->val = i;
    }
    p->next = head;
    
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m - 1; j++) {
            head = head->next;
        }
        struct ListNode *q = head->next;
        head->next = q->next;
        free(q);
        head = head->next;
    }
    
    return head->val;
}

发表于 2021-09-18 00:20:35 回复(0)
提交观点

问题信息

链表 基础数学
难度：
9条回答 4331浏览

热门推荐

通过挑战的用户

查看代码

相关试题

环形链表的约瑟夫问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号