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

8 Years
Discussion Span
Last Post by firstPerson

Whats confusing about it? Maybe some pics will help :

//initial list

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


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

Now we delete 3. So the list now is :


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.

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

//delete 6 and move pointer forward

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

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


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

Now we delete 2, and we get :


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


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


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 
       move( currentPointer , 2) ; //move current pointer 2 places forward
   return list.firstElement;
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.