DS循环链表—约瑟夫环

题目描述

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

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

要求使用循环链表实现。

输入

测试数据有多组

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

输出

出列的人的编号

#include<iostream>
using namespace std;
class node
{public:
	int data;
	node* next;
	node* prior;
	node()
	{
		data = 0;
		next = NULL;
		prior = NULL;
	}
};
class linklist
{
public:
	node* head;
	node* end;
	int len;
	linklist()
	{
		len = 0;
	}
	//创建循环链表
	void creat(int n)
	{
		len = n;
		node* p = new node;
		node* q = p;
		for (int i = 1; i <= n; ++i)
		{
			node* r = new node;
			r->data = i;
			q->next = r;
			q->prior = q;
			q = r;
			if (i == n)
			{
				q->next = p->next;
			}			
		}
		head = p->next;
	}
	void print()
	{
		node* p = head;
		int i = 0;
		while (i!=len)
		{
			cout << p->data ;
			if (i != len - 1)
			{
				cout << " ";
			}
			i++;

			p = p->next;
		}
		cout << endl;
	}
	linklist merge(int k, int s)
	{
		linklist a;
		node* qq = new node;
		node* q = qq;
		node* p = head;
		int i = 1;
		int l = 0;
		while (len!=1)
		{
			if (i == s)
			{
				int j = 1;
				while (j != k - 1)
				{
					j++;
					p = p->next;
				}
				node* r = p->next;
				q->next = r;
				l++;
				len--;
				q = r;
				p->next=r->next;
				i--;
			}
			i++;
			p = p->next;
		}
		node* r = new node;
		r->data = p->data;
		q->next = r;
		q = r;
		l++;
		a.head = qq->next;
		a.len = l;
		return a;
	}
};
int main()
{
	int n, k, s;
	while (cin >> n >> k >> s)
	{
		linklist a;
		a.creat(n);
		linklist p = a.merge(k, s);
		p.print();		
	}
}