The best way to start figuring out a complicated and confusing
problem is to think about examples. Suppose your list is
7,3,6,5,8,7. The `*`

indicates the correct positions for
`p`

on successive calls to `next`

:

7 *3 6 5 3 3 8 7 p is initially chosen by the constructor 7 3 6 5 *3 3 8 7 7 3 6 5 3 *3 8 7 7 3 6 *5 3 3 8 7 7 3 *6 5 3 3 8 7 *7 3 6 5 3 3 8 7 7 3 6 5 3 3 8 *7 7 3 6 5 3 3 *8 7 7 3 6 5 3 3 8 7 p==null, no more elements

So `p`

will point to the three 3's in left to right order, then the 5,
then the 6, then the two 7's in left to right order, and finally the
8.

Keep thinking about it. You will definitely learn more if you try hard to figure it out by yourself! Once you think you've got a solution (or if you're really, really stuck), you can check out this further hint.

Jason Eisner - `jason@cs.jhu.edu`

- *$Date: 2004/02/18 07:14:59 $*