学步园

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;
int jph(int & n,int & k);


//利用一个双向循环链表去模拟约瑟夫环
struct Node
{
 int num;
 Node *pre;
 Node * next;
};


int main()
{
 int n,k;
 
  while(scanf("%d %d",&n,&k)!=EOF)
          printf("%d\n",jph(n,k)); 
return 0;
}



int jph(int & n,int & k)
{
//生成双向循环链表
  Node *front;//头指针
  Node *rear;//尾指针

   Node *ptr=new Node;
    ptr->num=1;
    ptr->next=NULL;
    ptr->pre=NULL;
    front=ptr;
    rear=ptr;
    
  for(int i=2;i<=n;++i)
  {
    Node *ptr=new Node;
    ptr->num=i;
    ptr->next=NULL;
    ptr->pre=rear;
    rear->next=ptr;
    rear=ptr;
    
  }
  
  //使之成为双向循环链表
  rear->next=front;
  front->pre=rear;
  
  int c;
  
  for(c=1;front->next!=front;)//如果首尾指针指向了自己，则链表中只剩下一个元素即为所求
  {
     if(c==k)//计数器到时，则删除该节点
     {
       Node * p=front;
       front=front->next;
       p->pre->next=p->next;
       p->next->pre=p->pre;
       delete p;
       c=1;
       
     }
     else
     {
       ++c;
       front=front->next;
     }
     
  }
  
  int ret=front->num;
  delete front;
  
  return ret;
}