circular linked list

[virtualsansar]

how to create circular linked list for the following situation?
If there is upto n number like
123456 initial list, start counting from 1
12456 no. 3 eliminated, continue counting from 4
1245 no. 6 eliminated, continue counting from 1
125 no. 4 eliminated, continue counting from 5
15 no. 2 eliminated, continue counting from 5
1 no. 5 eliminated, 1 is lucky

[mrnutty]

Whats confusing about it? Maybe some pics will help :

//initial list
1->2->3->4->5->6

If I put [] around a number then thats the current pointer pointing to.
So the pointer starts pointing to 1 so :

[1]->2->3->4->5->6

Let P1 be the current pointer, then from your psuedocode, we delete
(P1+2). Since our pointer is pointing to 1, we delete (1+2), or the third element, which is 3, so:

//move our pointer two places
1->2->[3]->4->5->6

Now we delete 3. So the list now is :

1->2->[4]->5->6

Notice, the current pointer moves forward, when the element its pointing to gets deleted. Now again, we move 2 places from our
current pointer so :

//move from 4 to two places forward, into 6.
1->2->4->5->[6]

Now we delete the element that the pointer is pointing to, thus :

//delete 6 and move pointer forward
[1]->2->4->5

Since we delete 6, and since this is a circular list, instead of pointer pointing to null, it now loops back to 1.
Now we move the pointer two places forward and delete it, so :

//move two places from 1 and delete that element
1->2->[4]->5

Now 4 gets deleted, and the pointer is now pointing to 5. So,

1->2->[5]

Now move the pointer 2 places, since this is a circular loop, it loops back from 5, when you move forward so, moveing 2 places from 5, we get :

//move two places from 5, and delete the element that the pointer is on
1->[2]->5

Now we delete 2, and we get :

1->[5]

Now we move 2 places forward from 5, again, and we get :

1->[5]

Now we delete the element the current pointer is pointing to , thus
5 gets deleted and we are left with :

1

and whala, we have only 1 element left, so we stop, and 1 becomes the winner.

In pusedocode, here is one way you can do it :

T pickSpecialWinner(CircularList& list){
  assert(list.size()); //make sure good size
  if(list.size() == 1) return firstElement;
  
  set currentPointer to list.firstElement
  while list.size is greater than 1 
   do
       move( currentPointer , 2) ; //move current pointer 2 places forward
       delete(currentPointer);
   endOfDo
  
   return list.firstElement;
}