Does this algorithm on a circular linked list ever terminate?

Question

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?

Answer 1

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.