C. DS循环链表—约瑟夫环 (Ver. I - B)

题目描述

N个人坐成一个圆环（编号为1 - N），从第S个人开始报数，数到K的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。

例如：N = 3，K = 2，S = 1。2号先出列，然后是1号，最后剩下的是3号。

测试数据有多组，

每组包括3个数N、K、S，表示有N个人，从编号为S的人开始，数到K出列。

输入

测试数据有多组

每组包括3个数N、K、S，表示有N个人，从第S个人开始，数到K出列。(2 <= N <= 10^3，10^3 < K <= 10^9,  1 <= S <= N)

输出

出列的人的编号

输入样例1：

13 3 1
3 2 1

输出样例1：

3 6 9 12 2 7 11 4 10 5 1 8 13 
2 1 3 

AC代码：

#include <iostream>
using namespace std;
class node
{
public:
    int data;
    node* next;
    node():data(0),next(nullptr){}
};

class linklist
{
    int len;
    node* head;
public:
    linklist()
    {
        head=new node;
        head->data=1;
        head->next=head;
    }
    void create(int n)
    {
        node* tail=head;
        for(int i=2;i<=n;i++)
        {
            node* p=new node;
            p->data=i;
            tail->next=p;
            p->next=head;
            tail=p;
        }
        tail->next=head;
        len=n;
    }
    void print(int k,int s)
    {
        node* p=head;
        for(int i=1;i<s;i++)
        {
            p=p->next;
        }
        while(len)
        {
            int k1=k;
            k1=k1%len+len;
            for(int i=1;i<k1-1;i++)
            {
                p=p->next;
            }
            node* q=p->next;
            cout<<q->data<<" ";
            p->next=q->next;
            delete q;
            p=p->next;
            len--;
        }
        cout<<endl;
    }

};
int main()
{
    int n,k,s;
    while(cin>>n>>k>>s)
    {
        linklist L;
        L.create(n);
        L.print(k,s);
    }
    return 0;
}