Passing by Pointer Issue

Question

I'm trying to implement my own version of a linked list for learning. I have the following code. The reverseList function works correctly and if I print it inside that function it is good.

However, when I leave the function and then call the print method I get the the first value and then nothing (null). I'm guessing when I get out of the function it brings me back to the original first ([99]) element which is now actually the last element. So my print method outputs the element sees null is the next and ends.

Or I was thinking the changes I was making in the function were somehow only in that function's scope even though I passed a pointer, but that doesn't make sense because if that's the case then I should have all the original data still.

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

Appreciative of any help you guys can give me,

Thanks!

Answer 1

Update: By passing the ListNode *list to reverseList, you create a copy of your pointer which point to the same address with nodes. Inside the function, you assign list to the updated cur pointer but the copy will be destroyed at the end. list still points to the same address as before passing to reverseList but its next has changed.

I have modified your code a little bit:

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

Try to compile with: -std=gnu++11

Answer 2

Reversing a linked list is not a fundamental operation. It does not belong among the basis operations of your class. It is easier (and safer) to implement it in terms of your other operations. Roughly:

• Create an empty list.
• While the first list is not empty, remove a node from the front of the first list and insert it into the front of the second list.

The second list is now the reverse of the original.

Answer 3

You don't change nodes in reverseList you're just changing list you're just changing a pointer on your struct which is a temporary object so physically nodes steel the same and pointed on the same first element which now has next attribute pointing on Null so the result of printList is correct. You need to work with pointers e.g.

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

Also, don't forget to delete object created dynamically