我要招人

去企业版

首页 > 试题广场 >

环形链表的约瑟夫问题

[编程题]环形链表的约瑟夫问题

热度指数：23131 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。

下一个人继续从 1 开始报数。

n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

数据范围： $1 \le n , m \le 10000$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

5,2

输出

说明

开始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

输出

算法知识视频讲解

区欠阳

 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)

温柔的卡尔被发好人卡

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)

牛客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)

牛客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)

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)

木鱼脑壳儿

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)

牛客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)