Связанный список обратный без использования цикла?

Question

Меня спросил один из моих старших руководителей: можно ли перевернуть односвязный список без использования цикла? Если да, то как? Его улыбка, казалось, говорила мне, что это возможно, но я ничего не мог придумать. Кто-нибудь думал об этом раньше?

Answer 1

Можно отменить двойной связанный список в O (1) путем замены его head и tail указатели, и (в зависимости от реализации) установление своего рода флаг, который скажет, что список должен быть теперь повторяется назад (т. е. следуя указателям back для повторения итерации вперед и следуя указателям next, чтобы итератировать назад).

Что касается односвязного списка, я считаю, что его невозможно отменить быстрее, чем O (n).

Answer 2

В STL есть итераторы rbegin() и rend() для обхода коллекций в обратном порядке. Но он не будет работать для одного связанного списка.

Answer 3

подход в рекурсии

struct node { 
    int value; 
    struct node* next; 
}; 

struct node** _reverse(struct node* n) 
{ 
    if (NULL != n->next) 
     *_reverse(n->next) = n; 
    return &(n->next); 
} 

// this is the entry 
void reverse(struct node* head) 
{ 
    *_reverse(head) = NULL; 
}