Printing a strings linked list lexicographically, time O(n^2), space O(1), no swap

[Billy]

Hi,

It has to be some stupid high school home task , that can be solved in
rather straightforward manner.
The pain in the @ss is the requirement not to touch the original list,
that is: no swap between the elements is permitted.
O(n^2) is a bunch of time: the list can be even bubble sorted, but I
really fail to figure out how the hell I'm supposed to handle the
sorting without building any additional structures and the requirement
not to modify the original list in any way.

Any help/tip/advice will be appreciated,

Thanks.

[Richard Harter]

On 8 Jan 2007 22:33:41 -0800, "Billy" <st******@gmail.comwrote:

>Hi,

It has to be some stupid high school home task , that can be solved in
rather straightforward manner.
The pain in the @ss is the requirement not to touch the original list,
that is: no swap between the elements is permitted.
O(n^2) is a bunch of time: the list can be even bubble sorted, but I
really fail to figure out how the hell I'm supposed to handle the
sorting without building any additional structures and the requirement
not to modify the original list in any way.

Any help/tip/advice will be appreciated,

Wrong news group. That said, make n passes through the list. In each
pass find the smallest one that is larger than the last one printed.
Try comp.programming next time.

[David T. Ashley]

"Richard Harter" <cr*@tiac.netwrote in message
news:45***************@news.sbtc.net...

On 8 Jan 2007 22:33:41 -0800, "Billy" <st******@gmail.comwrote:

>>Hi,

It has to be some stupid high school home task , that can be solved in
rather straightforward manner.
The pain in the @ss is the requirement not to touch the original list,
that is: no swap between the elements is permitted.
O(n^2) is a bunch of time: the list can be even bubble sorted, but I
really fail to figure out how the hell I'm supposed to handle the
sorting without building any additional structures and the requirement
not to modify the original list in any way.

Any help/tip/advice will be appreciated,

Wrong news group. That said, make n passes through the list. In each
pass find the smallest one that is larger than the last one printed.
Try comp.programming next time.

Also, Billy, although I'm sure you noticed ... making N complete passes
through a list with N elements might be O(N**2).