130 - Roman Roulette

// romanR.cpp : Defines the entry point for the console application.
//

#include <iostream>
using namespace std;

struct node
{
int data;
struct node * next;
};

typedef struct node point;

point * startPoint=NULL;

void createCircularList(int N)
{
point * nextPoint;
for(int i=1;i<=N;i++)
{
  if(startPoint==NULL)
{
startPoint=new node();
startPoint->data=1;
startPoint->next=NULL;
nextPoint=startPoint;
}
else
{
point * newPoint=new point();
newPoint->data=i;

nextPoint->next=newPoint;
newPoint->next=startPoint;
nextPoint=newPoint;
}
}
}

void showAllNode()
{
point * temp=startPoint;

while(temp!=NULL)
{
cout<<temp->data<<" ";
if(temp->next==startPoint)
{
break;

}
else
{
temp=temp->next;
}
}
cout<<endl;
}
void destroyCircle(int n)
{
point * last=startPoint;


point * toDelete=startPoint;
for(int i=0;i<n;i++)
{
if(toDelete!=NULL)
{
point *temp=toDelete->next;
delete toDelete;
toDelete=temp;
}
}
startPoint=NULL;
}
int GetSafePosition(int n,int k)
{
point * temp=startPoint;
int total=n;
//int returnVal=startPoint->data;
point * toBeKilled=temp;
point * toBeReplaced;

while(total>1)
{
int needToSkipped=0;

do
{
if(needToSkipped>=k)
{
break;
}
else
{
if(toBeKilled->data>0)
{
needToSkipped++;
if(needToSkipped>=k)
break;
}
toBeKilled=toBeKilled->next;
}

}while(1);

needToSkipped=0;
toBeReplaced=toBeKilled->next;

do
{
if(needToSkipped>=k)
{
break;
}
else
{
if(toBeReplaced->data>0 && toBeReplaced!=toBeKilled)
{
//cout<<toBeReplaced->data<<endl;
needToSkipped++;
if(needToSkipped>=k)
break;
}
toBeReplaced=toBeReplaced->next;
}

}while(1);
//cout<<"To be killed "<<toBeKilled->data<<" to be replaced "<<toBeReplaced->data<<endl;
toBeKilled->data=toBeReplaced->data;
//returnVal=toBeKilled->data;
toBeReplaced->data=0;
total--;
//showAllNode();
toBeKilled=toBeKilled->next;
}

while(temp->data==0)
{
temp=temp->next;
}

//cout<<"show all the nodes"<<endl;
//showAllNode();


return (n-temp->data+1)%n+1;

}
void RomanRoulette(int n,int k)
{
if(n==1)
{cout<<1<<endl; return;}
if(k==0)
{cout<<1<<endl; return;}

createCircularList(n);
//showAllNode();
cout<<GetSafePosition(n,k)<<endl;
//showAllNode();
destroyCircle(n);
}

int main()
{
int n=0,k=0;
while(1)
{
cin>>n>>k;
if(n==0 && k==0)
{
break;
}
RomanRoulette(n,k);
}


return 0;
}