Реверсивный односвязный список с использованием рекурсии - PullRequest
Новая
       18

Реверсивный односвязный список с использованием рекурсии

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

Я написал код для обратного односвязного списка с помощью рекурсии.Он работает нормально для списков длиной меньше или равных 174725. Но для списков длины больше 174725 он дает ошибку сегментации (Ошибка сегментации: 11) при обращении к ней с помощью функции reverse ().Может кто-нибудь, пожалуйста, объясните мне это? 

#include <iostream>
using namespace std;

class Node
{
  public:
    int val;
    Node *next;
};

class Sll
{
  public:
    Node *head;

  private:
    void reverse(Node *node);

  public:
    Sll();
    void insert_front(int key);
    void reverse();
    void print();
};

void Sll::reverse(Node *node)
{
    if (node == NULL) return;
    Node *rest = node->next;
    if (rest == NULL)
    {
        head = node;
        return;
    }
    reverse(rest);
    rest->next = node;
    node->next = NULL;
    return;
}

Sll::Sll()
{
    head = NULL;
}

void Sll::insert_front(int key)
{
    Node *newnode = new Node;
    newnode->val = key;
    newnode->next = head;
    head = newnode;
    return;
}

void Sll::print()
{
    Node *temp = head;
    while (temp)
    {
        temp = temp->next;
    }
    cout << endl;
    return;
}

void Sll::reverse()
{
    reverse(head);
    return;
}

int main()
{
    Sll newList = Sll();
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) newList.insert_front(i + 1);
    newList.reverse();
    // newList.print();
    return 0;
}

1 Ответ

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

Функция обращения к списку должна быть хвостовой рекурсивной, иначе она будет переполнять стек при повторении по длинному списку, как вы заметили.Кроме того, его нужно скомпилировать с включенной оптимизацией или с опцией -foptimize-sibling-calls gcc.

Хвосто-рекурсивная версия: 

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;
}
...