Сторнирование связанного списка с помощью рекурсии - PullRequest
Новая
       31

Сторнирование связанного списка с помощью рекурсии

0 голосов
/ 02 июня 2018

Я хочу иметь возможность написать рекурсивную функцию для обращения к связанному списку.Представьте, что все элементы уже добавлены в список.

Я хочу назначить head-> next-> рядом с head, поэтому следующим узлом узла-> next является сам узел.Затем, когда рекурсия завершена, присвойте заголовок связанного списка (this-> head) конечному узлу (который является head).

Чего также не хватает, так это присвоению конечного узла рядом с NULL.

Будет ли в каком-либо мире что-то подобное работать?Выдает ошибку времени выполнения / сегментации. 

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

class LinkedList{
    node *head = nullptr;
public:
    node *reverse(node *head){
        if(head->next != nullptr){
            reverse(head->next)->next = head;
        }
        else{
            this->head = head;
        }
        return head;
    }
};

Ответы [ 2 ]

0 голосов
/ 03 июня 2018

Функция обращения к списку должна быть хвостовой рекурсивной, в противном случае она будет переполнять стек при повторном обращении к длинному списку.Например: 

node* reverse(node* n, node* prev = nullptr) {
    if(!n)
        return prev;
    node* next = n->next;
    n->next = prev;
    return reverse(next, n);
}

Итеративную реверсию списка можно встроить проще: 

inline node* reverse(node* n) {
    node* prev = nullptr;
    while(n) {
        node* next = n->next;
        n->next = prev;
        prev = n;
        n = next;
    }
    return prev;
}
0 голосов
/ 02 июня 2018

Обратите внимание, что вы игнорируете случай, когда голова * nullptr сама.Кроме того, вы не можете просто вернуть head ... вам нужно вернуть заголовок списка перевернутый .

Попробуйте это: 

node* reverse_list(node* head) {
    if (head == nullptr or head->next == nullptr) { return head; }
    auto tail = head->next;
    auto reversed_tail = reverse_list(tail);
    // tail now points to the _last_ node in reversed_tail,
    // so tail->next must be null; tail can't be null itself        
    tail->next = head; 
    head->next = nullptr;
    return reversed_tail;
}

(не проверено ...)

...