题目描述

0,1,...这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里最后一个数字。

思路

这道题就是有名的约瑟夫环问题，有两种解题方法
(1)环形链表模拟圆圈
(2) 分析每次被删除的数字的规律并直接计算出圆圈中最后剩下的数字

方法1：环形链表模拟圆圈

构造一个循环链表，每次在这个链表中删除第m个节点
注意：牛客里好像已经定义了节点，如果没有的话需要自己进行定义

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n<=0||m<=0)
            return -1;
        //构造循环链表
        ListNode* head=new ListNode(0);  //头结点
        ListNode* pre=head;
        ListNode* temp=NULL;
        for(int i=1;i<n;i++)
        {
            temp = new ListNode(i);
            pre->next=temp;
            pre=temp;
        }
        pre->next=head;//将第n-1个节点指向头结点
        temp=head;//开始从头进行删除操作
        while(n!=1)
        {
            for(int i=0;i<m-2;i++)//注意这里什么时候停下来进行删除操作
                temp=temp->next;
            temp->next=temp->next->next;//删除temp后面的节点
            head=temp->next;
            temp=head;
            n--;
        }
        return temp->val;
    }
};

方法二(归纳出最后剩下的数字)