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.
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? $\endgroup$ – Patrick87 Aug 11 '14 at 22:23