# Does this algorithm on a circular linked list ever terminate?

Suppose we have a circular linked list that has nodes $1$ to $n$. L is a pointer that points to node 1 (with label $1$). Note i has a link to i+1 and we have a link from node n to node 1 because the list is circular.

Now we have following pesudo-code:

Int SO(LIST *L) {

While ( L->Next != L ) {
L->Next = L->Next->Next;
L = L->Next;
}

return L->Data;
}


The question is: what is the output for $n=729$ and $n=2200$ what is the output of the above code.

My solution: I check the pesudo-code. My idea is this code has a problem and L and L->Next never become equal so an infinite loop occurs. Is this correct?

• Execute the code for $n=3$ and $n=4$. What happens? (Hint: the big number is only to force you to understand, not dumbly execute. Use small examples to faciliate this understanding, then generalise.) – Raphael Aug 11 '14 at 17:09
• I mean you have to think more (carefully) on this; either you find a proof for your claim (currently you don't present one) or you find that you are wrong, and find a proof of the contrary. Hint 2: note how the list changes during the iteration. – Raphael Aug 11 '14 at 17:16
• To expand on Raphael's hint, try a few iterations, and after each iteration, list the elements in the list as follows: starting from the current element, follow the Next pointers until you end up where you started. Then, perform another iteration of the loop body, and list the elements in the list in like manner. Pay special attention to the number of elements you enumerate after each iteration of the loop body. Convince yourself that the loop body effectively "hops over" an element at a time, "cutting it out" of the circuit. You can only remove so many links from a chain before... what? – Patrick87 Aug 11 '14 at 22:23

The algorithm will always terminate. Look at the case where $n=2$. Initially we'll have 1->next = 2 and 2->next = 1. In the first iteration we'll change 1->next to 1->next->next = (1->next)->next = 2->next = 1 so 1->next will point to 1 and the loop termination condition applies, so we bail and return 1->data.
If $n>2$, every iteration of the loop will point around a node, eliminating it forever from consideration, so every iteration of the loop decreases the number of nodes in play, so we'll always get to the $n=2$ case eventually and then halt.
It might help to think of this as the nightmarish situation where a group of $n$ people have been captured by bloodthirsty pirates. The pirates arrange the group in a circle and, starting at person 1, go around the circle, shooting every other person until only one remains. Where do you want to position yourself so that you are the last surviving person?
This is a well-known problem, called the problem of Josephus, and is often assigned as an exercise in a beginning programming class. The solution is nifty: Given $n$, write it as $n=2^m+k$, where $0\le k < 2^m$, then the last survivor is the one in initial position $2k+1$ (starting at position 1). Given this, we have that with $n=729$ the survivor will be the one in position 435 and with $n=2200$ the survivor (after a heck of a lot of shooting) will be the one in initial position 305.