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

2
Contributors
1
2
Views
8 Years
Discussion Span
Last Post by firstPerson

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;
}``````
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.