Проходя по проблеме указателя

Question

Я пытаюсь реализовать собственную версию связанного списка для обучения. У меня есть следующий код.Функция reverseList работает правильно, и если я распечатаю ее внутри этой функции, это хорошо.

Однако, когда я покидаю функцию и затем вызываю метод print, я получаю первое значение, а затем ничего (ноль).Я предполагаю, что когда я выхожу из функции, она возвращает меня к первоначальному первому ([99]) элементу, который теперь фактически является последним элементом.Поэтому мой метод печати выводит, что элемент видит нулевое значение следующим и завершается.

Или я думал, что изменения, которые я делал в функции, были каким-то образом только в области действия этой функции, даже если я передал указатель, но это неЭто не имеет смысла, потому что если это так, то я должен иметь все исходные данные.

struct ListNode
{
    int value;
    ListNode* next = NULL;
};

void insertRecList(ListNode* list, int value)
{
    if(list->next == NULL)
    {
        ListNode* end = new ListNode;
        end->value = value;
        list->next = end;
    }
    else
        insertRecList(list->next, value);
}

void printList(ListNode* list)
{
    std::cout << list->value << std::endl;
    while(list->next != NULL)
    {
        list = list->next;
        std::cout << list->value << std::endl;
    }
}

void reverseList(ListNode* list)
{
    ListNode* next;
    ListNode* prev  = NULL;
    ListNode* cur   = list;

    while(cur != NULL)
    {
        if(cur->next == NULL)
        {     
            cur->next = prev;
            break;
        }
        else
        {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
    }
    list = cur;
    std::cout << cur->value << " list:" <<  list->value << std::endl;

}

void testLinkedList()
{
    srand(time(NULL));

    ListNode nodes;
    nodes.value = 99;
    int val;

    for(int i = 0; i < 5; i++)
    {
        val = rand() % 30 + 1;
        insertRecList(&nodes, i);
        //insertList(&nodes, val);
    }
    printList(&nodes);
    reverseList(&nodes);
    printList(&nodes);
}

int main()
{
    testLinkedList();
    return 0;
}

Благодарю за любую помощь, которую вы, ребята, можете оказать мне,

Спасибо!

Answer 1

Сторнирование связанного списка не является фундаментальной операцией.Он не принадлежит к числу базовых операций вашего класса.Это проще (и безопаснее) реализовать с точки зрения других ваших операций.Примерно:

• Создайте пустой список.
• Пока первый список не пустой, удалите узел в начале первого списка и вставьте его в начало второго списка.

Второй список теперь обратен оригиналу.

Answer 2

Вы не изменяете nodes в reverseList вы просто меняете list вы просто меняете указатель на вашу структуру, которая является временным объектом, поэтому физические узлы стали одинаковыми и указали на то же самое в первую очередь элемент, который теперь имеет атрибут next, указывающий на Null, поэтому результат printList правильный. Вам нужно работать с указателями, например

#include <iostream>
#include <cstdlib>


struct ListNode
{
    int value;
    ListNode* next = NULL;
    ~ListNode(){
        if(this->next)
            delete this->next;
    }
};

void insertRecList(ListNode* list, int value)
{
    if(list->next == NULL)
    {
        ListNode* end = new ListNode;
        end->value = value;
        list->next = end;
    }
    else
        insertRecList(list->next, value);
}

void printList(ListNode* list)
{
    std::cout << list->value << std::endl;
    while(list->next != NULL)
    {
        list = list->next;
        std::cout << list->value << std::endl;
    }
}

ListNode * reverseList(ListNode* list)
{
    ListNode* next;
    ListNode* prev  = NULL;
    ListNode* cur   = list;

    while(cur != NULL)
    {
        if(cur->next == NULL)
        {
            cur->next = prev;
            break;
        }
        else
        {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
    }
    std::cout << cur->value << " list:" <<  list->value << std::endl;
    return cur;
}

void testLinkedList()
{
    srand(time(NULL));

    ListNode * nodes = new ListNode;
    nodes->value = 99;
    int val;

    for(int i = 0; i < 5; i++)
    {
        val = rand() % 30 + 1;
        insertRecList(nodes, i);
        //insertList(&nodes, val);
    }
    printList(nodes);
    nodes = reverseList(nodes);
    printList(nodes);
    delete nodes;
}

int main()
{
    testLinkedList();
    return 0;
}

Также не забудьте удалить объект, созданный динамически

Answer 3

Обновление: передавая ListNode *list в reverseList, вы создаете копию вашего указателя, которая указывает на тот же адрес с nodes.Внутри функции вы присваиваете list обновленному указателю cur, но в конце копия будет уничтожена.list по-прежнему указывает на тот же адрес, что и до перехода к reverseList, но его next изменилось.

Я немного изменил ваш код:

#include <cstdlib>
#include <iostream>

struct ListNode
{
    int value;
    ListNode* next = nullptr;
};

void insertRecList(ListNode* list, int value)
{
    if(list->next == nullptr)
    {
        ListNode* end = new ListNode;
        end->value = value;
        list->next = end;
    }
    else
        insertRecList(list->next, value);
}

void printList(ListNode* list)
{
    std::cout << list->value << std::endl;
    while(list->next != nullptr)
    {
        list = list->next;
        std::cout << list->value << std::endl;
    }
}

void reverseList(ListNode** list)
{
    ListNode* cur   = *list;
    ListNode* next  = cur->next;
    ListNode* prev  = nullptr;

    while(cur != nullptr)
    {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    *list = prev;
}

void cleanNodes(ListNode *list) {
    // clean goes here
}

void testLinkedList()
{
    srand(time(nullptr));

    ListNode *nodes = new ListNode();
    nodes->value = 99;
    int val;

    for(int i = 0; i < 5; i++)
    {
        val = rand() % 30 + 1;
        insertRecList(nodes, i);
        //insertList(&nodes, val);
    }
    printList(nodes);
    reverseList(&nodes);
    printList(nodes);

    cleanNodes(nodes);
}

int main()
{
    testLinkedList();
    return 0;
}

Попробуйтескомпилировать с: -std = gnu ++ 11