首页 > 试题广场 >

环形链表的约瑟夫问题

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

热度指数：24796 时间限制：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

输出

算法知识视频讲解

牛客461545158号

class Solution:
    def ysf(self , n , m ):
        # write code here
        res = [i + 1 for i in range(n)]
        i = 0
        for j in range(n-1):
            i = (i + m - 1) % (n - j)
            del res[i]
        return res[0]
    
    
# 取一个数组，循环删除

发表于 2021-01-17 11:11:07 回复(1)

Bug专家

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int ysf (int n, int m) {
        // write code here
        //先用列表记录各个数的下标位置
        if(n==1) return 1;
        List<Integer> list = new ArrayList();
        for(int i = 1;i<=n;i++){
            list.add(i);
        }
        //当前指针正指向的位置
        int cur = 0;
        while(list.size()>1){
            //当前遍历时还剩多少人
            int size = list.size();
            //当前列表要删除元素的下标
            cur = (cur+m-1)%size;
            //删除指定下标元素
            list.remove(cur);
        }
        //返回最后剩下人的下标
        return list.get(0);
    }
}

发表于 2022-07-14 13:36:38 回复(0)

勇敢牛牛，不怕困难！

struct Node {
  int val;
  Node* next;
  Node() : val(0), next(nullptr) {}
  Node(int _val) : val(_val), next(nullptr) {}
  Node(int _val, Node* _next) : val(_val), next(_next) {}
};

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int ysf(int n, int m) {
      Node* head = new Node(1), *tail = head; // 头尾指针
      for (int i = 2; i <= n; ++i) {
        Node* node = new Node(i);
        tail = tail->next = node; // 尾插手法
      }
      
      tail = tail->next = head; // 形成环
      for (int i = 0; i < n - 1; ++i) {
        for (int j = 1; j < m - 1; ++j)
          tail = tail->next;
        
        Node* node_to_delete = tail->next;
        tail = tail->next = tail->next->next;
        delete node_to_delete;
      }
      
      return tail->val;
    }
};

发表于 2021-07-13 08:16:34 回复(0)

Java

阿尼亚瓦库瓦库

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int ysf (int n, int m) {
        // write code here
        return f(n, m) + 1;
    }
    
    private int f (int n, int m) {
        if (n == 1) {
            return 0;
        }
        
        return (f (n - 1, m) + m) % n;
    }
}

递归解法

因为上述解法经常出现栈溢出的问题，所以这里提供使用list集合的解法：

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int ysf (int n, int m) {
        // write code here
        ArrayList<Integer> ysf = new ArrayList<>(); // list集合模拟约瑟夫环
        
        for (int i = 1; i <= n; i++) {
            ysf.add(i); // 装载人
        }
        
        int index = 0;
        
        while (ysf.size() != 1) {
           index = (index + m - 1) % ysf.size(); // 报数 直到指定的数
            ysf.remove(index); // 人出列
            // index = (index + 1) % ysf.size(); // 从出列的下一个人开始数数
            // 因为人出列了，所以这个index这个位置被出列后一个人占了，不需要进行处理了
        }
        
        return ysf.get(0);
    }
}

编辑于 2021-06-22 14:09:40 回复(0)

JavaScript

splwany

function ysf( n ,  m ) {
    if (n < 1 || m < 1) return null;
    let last = 0;
    for (let i = 2; i <= n; i++) last = (last + m) % i;
    return last + 1;
}

发表于 2021-04-18 16:01:35 回复(0)

hhh哦

约瑟夫环问题时间复杂度：O（n）空间：O（1）

/*
解设:  f(n,m) 表示 n 个编号，报号到 m 的最终那个编号
则： 为了方便取模，编号序列从 0 开始 即
1  2  3  4  5  6  ...  ,k-1,  k,  k+1, k+2  ... n
初始序列状态：
0  1  2  3  4  5  ...  ,k-2,  k-1   k, k+1  ... n-1
即 seq1 = [0,1,2...n-1]
递推：
那么 f(n,m) 与 f(n-1,m)有啥关系呢？
1. 假设第一轮取第 m 个数取到编号为 k 的序列， 即 k = (m-1) % n
2. 则取完后，f(n-1, m)的起点状态变化为：
0    1    2    3    4    5    ...  ,  k-2,    k-1,     k,   k+1   ...,n-2
k+1 k+2   k+3 k+4  k+5  k+6   ...  ,  n-1,    0  ,     1,   2     ...,k-1
设 seq2 = [k+1, k+2,..., 0, 1, 2, ..., k-1]
则 从seq1 映射到 seq2 函数为: g(x) = (x+k+1) % n  //根据地址里的序列变换到另一个序列
f(n,m,seq1) 表示 n 个元素，取第 m 个位置的，以seq1序列为内容的值，f对最终选取的位置与seq无关
= f(n-1, m, seq2)
= f(n-1, m, g(seq1))
= g(f(n-1, m, seq1)) 
//不管是序列seq1还是序列seq2，选择的第 m 个位置（地址）一定是相同的，所以可以先选位置，再交换空间内容
即
f(n,m) = g( f(n-1, m) )
	   = (f(n-1,m) + k + 1) % n         when k = (m-1) % n
f(1,m) = 0 // 1 个元素，选第 m 个元素一定是 0 （默认seq1顺序，不带seq形参）
*/
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     *///for循环搞定
    int ysf(int n, int m) {
        int ans = 0, k;
        for(int i = 1; i<n; ++i){
            k = (m-1)%(i+1);
            ans = (ans + k + 1)%(i+1);
        }
        return ans+1;
    }

};

编辑于 2021-04-16 22:47:52 回复(0)

Java

惠灵顿靖

import java.util.*;
public class Solution {
    public int ysf (int n, int m) {
        // write code here
        LinkedList<Integer> list = new LinkedList<>();
        for (int i=1;i<=n;++i){
            list.addLast(i);
        }
        int curr = 0;
        while (list.size() > 1){
            int size = list.size();
            int pos = (curr+m-1)%size;
            list.remove(pos);
//            // 当只剩下最后一个时候，令cur==0
//             if(size-1==1)
//                 curr=0;
//             else      //其实注释掉的这部分没有也可以，因为及时最后size为0了，curr为1，可是便立即结束了循环，不会边界溢出的
                curr=pos;
        }
        return list.get(0);
    }
}

发表于 2021-04-10 20:24:17 回复(0)

一心找工作的Leo

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int ysf (int n, int m) {
        // write code here
        ArrayList<Integer> ysf = new ArrayList<>();
        for(int i = 1; i <= n; i++){
            ysf.add(i);
        }
        int curr = 0;//当前位置
        while(ysf.size() > 1){
            int size = ysf.size();
            int removePos = (curr + m - 1) % size;//当前要被删除的节点的位置
            ysf.remove(removePos);
            curr = removePos % (size - 1); //当前起点的位置。如果删除的是最后一个重置curr为0。      
        }
        return ysf.get(0);
    }
}
// 1 2 3 4 5 -> 1 3 4 5 -> 1 3 5 -> 3 5 -> 3

发表于 2021-03-06 07:52:42 回复(0)

木析

知道这么个思路，还推了半天的公式，还WA了几次才推出来……

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int ysf(int n, int m) {
//         if(n==1)
//             return 0;
        int x=0; //编号从0开始
        for(int i=2;i<=n;++i)
            x=(x+m)%i;
        return x+1;
    }
};

发表于 2021-07-09 20:06:46 回复(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)

我是一枚快乐的小菜鸡

题目说了用环形链表解决，那就先创建环形，然后挨个数就可以了。

class Solution {
public:
    ListNode* createList(int n) {
        ListNode *head = new ListNode(1);
        ListNode *p = head;
        for(int i = 2; i <= n; i++) {
            ListNode *node = new ListNode(i);
            p->next = node;
            p = node;
        }
        p->next = head;
        return head;
    }
    
    int ysf(int n, int m) {
        ListNode *head = createList(n);
        ListNode *p = head, *pre = NULL;
        while(p->next != p) {
            for(int i = 1; i < m; i++) {
                pre = p;
                p = p->next;
            }
            // 删除结点p
            pre->next = p->next;
            delete p;
            p = pre->next;
        }
        return p->val;
    }
};

发表于 2020-10-10 17:13:08 回复(2)

像风一样～～

import java.util.*;
public class Solution {
    public int ysf (int n, int m) {
        // write code here
        LinkedList<Integer> list = new LinkedList<>();
        for (int i=1;i<=n;++i){
            list.addLast(i);
        }
        int curr = 0;
        while (list.size() > 1){
            int size = list.size();
            int pos = (curr+m-1)%size;
            list.remove(pos);
            curr = pos % (size-1);    // 若删除的是最后一个，重置curr为0
        }
        return list.get(0);
    }
}

发表于 2021-02-23 15:43:12 回复(0)

Java

callmejacky

环形链表，占个地方😀😀

import java.util.*;


public class Solution {

    static class Ring{
        // 单向环形链表
        class RingNode{
            int val;
            RingNode next;

            public RingNode(int val){
                this.val = val;
                this.next = null;
            }
        }

        public RingNode head = null;
        public RingNode tail = null;
        public RingNode cur = null;

        // 添加元素
        public void add(int val){
            if(head == null){
                head = new RingNode(val);
                head.next = head;
                cur = head;
                tail = head;
            }else{
                // 新添加的元素放在循环链表的末尾
                tail = new RingNode(val);
                tail.next = head;
                cur.next = tail;
                cur.next.next = head;
                cur = cur.next;
            }
        }

        // 删除元素
        public boolean delete(int m){
            // 循环链表中只剩余一个元素
            if(head.next == head){
                return false;
            }

            // 确定待删除的元素
            RingNode todel = cur;
            for(int i = 1; i < m; i++){
                cur = todel;// cur移动到待删除的元素的前一个位置
                todel = todel.next;
            }

            // 待删除的元素为从当前节点开始的第二个指针
            if(head == todel){
                // 待删除的节点是头指针
                head = head.next;
                tail.next = head;
                cur = head;
            }else if(tail == todel){
                // 待删除的节点是尾指针
                RingNode p = head;
                while(p.next != tail){
                    p = p.next;
                }
                tail = p;
                tail.next = head;
                cur = head;
            }else{
                // 待删除的节点不是头尾指针
                cur.next = todel.next;
                cur = todel.next;
            }

            return true;
        }
    }

    /**
     *
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    public int ysf (int n, int m) {

        Ring ring = new Ring();
        // 添加元素到队列中
        for(int i = 0; i < n; i++){
            ring.add(i + 1);
        }
        // 将当前节点重新定位到头结点
        ring.cur = ring.head;
        // 循环删除
        while(ring.delete(m));

        return ring.head.val;
    }
}

发表于 2020-09-28 12:37:48 回复(1)

夜雨潇湘人断肠

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++

gap

逗号相隔的数据怎么输入如5，2 cstdio

编辑于 2024-03-01 19:22:06 回复(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)

唐氏综合征

只给出递归算法解释：

ysf(n-1, m) 表示上一轮落到的编号， ysf(n-1, m) -1 表示编号对应的下标，+ m 表示要走多少步， %n 表示最终落到哪个编号的下标，+1 表示改下标的编号，因为编号从1开始算，编号 = 下标 + 1

    public int ysf (int n, int m) {
        // write code here
        return n == 1 ? 1 : (ysf(n - 1, m) + m - 1) % n + 1;
    }

迭代法，逆向思维，也比较简单，略

发表于 2024-06-28 23:39:58 回复(0)

清风xu来

typedef struct ListNode ListNode;

ListNode* BuyNode(int x)

{

ListNode* newNode=(ListNode*)malloc(sizeof(ListNode));

if(newNode==NULL)

{

exit(1);

}

newNode->next=NULL;

newNode->val=x;

return newNode;

}

ListNode* CreateCircular(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 ptail;

}

int ysf(int n, int m )

{

ListNode* prev=CreateCircular(n);

ListNode* pcur=prev->next;

int count=1;

while(pcur->next!=pcur)

{

if(count!=m)

{

prev=pcur;

pcur=pcur->next;

count++;

}

else

{

prev->next=pcur->next;

free(pcur);

pcur=prev->next;

count=1;

}

return pcur->val;

}

发表于 2024-06-21 01:10:16 回复(0)

__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)

区欠阳

 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)