Odwracanie listy

Jak można odwrócić podwójnie łącząne listę w czasie O(1) ? W czasie O(n) wiem jak zrobić ale w O(1) nic mi do głowy nie przychodzi. Ma ktoś jakiś pomysł?

Zamienic glowe z ogonem? oraz traktowac nastepniki jako poprzedniki i vice versa...

traktować następnik jako poprzednik hmm... rozumiem, że musiałbym wtedy dać jakiegoś ifa, który by sprawdzał w którą stronę aktualnie mam się przemieszczać?

Cos w tym stylu, tak jak piszesz. Ustawiasz flage, ze jest jest na odwrot i wszelkie wywolania do next sa do prev i vice versa. Albo zrobic tablice, np. next_prev_tab[0]=next, next_prev_tab[1]=prev i manipulowac indeksem, czyli np.

exchange_head_with_tail();
REVERSE_FLAG = !REVERSE_FLAG;
if(REVERSE_FLAG)
{
  next_index = 1;
  prev_index = 0;
}
else
{
  next_index = 0;
  prev_index = 1;
}

I w operacjach uzywac zamiast

head->next...

tego

head->next_prev_tab[next_index];

I dzieki temu nie marnujesz taktow na ify za kazdym razem, tylko przy zmianie kolejnosci kolejki. Zlozonozc zamiany jak widac O(1), do korzystanie z kolejki nie zwalnia, bo dochodzi tylko odwolanie do elementu tablicy, czyli tez O(1).

Niezłe... Dzięki Johny :-)