Reversing a linked last causes "write access violation - temp was nullptr"

Question

Trying to reverse a linked list. I have tried everything - it gives me 'write access violation - temp was nullptr' on the following line:

temp->next = reversed.top();

More context:

struct ListNode {
    int data;
    ListNode* next;
    ListNode() : data(0), next(nullptr) {}
    ListNode(int value) : data(value), next(nullptr) {}
    ListNode(int value, ListNode* pointer) : data(value), next(pointer) {}
    
};

int main()
{
    ListNode* third = new ListNode(12, nullptr);
    ListNode* second = new ListNode(8, third);
    ListNode* head = new ListNode(5, second);

    stack<ListNode*> reversed;
    ListNode* temp = head;
    while (temp) {
        // Push all the nodes in to stack
        reversed.push(temp);
        temp = temp->next;
    }
    head = temp;
    while (!reversed.empty()) {
        // Store the top value of stack in list
        temp->next = reversed.top();
        // Pop the value from stack
        reversed.pop();
        // update the next pointer in the list
        temp = temp->next;
    }
    temp->next = nullptr;
}

What is a `stack`, here? Is that an `std::stack` or your own class? — Nathan Pierson, Jan 02 '23 at 07:55
When the first loop `while (temp)` ends, where is `temp` pointing? What is the value of `temp`? Some simple [rubber duck debugging](https://en.wikipedia.org/wiki/Rubber_duck_debugging) should help you understand the issue. — Some programmer dude, Jan 02 '23 at 07:57
But let's just walk through this program step by step. After your `while(temp)` loop exits, `reversed` will have 3 elements in it and `temp` will be `nullptr`. You then immediately attempt to set `temp->next = reversed.top();`. Does that make sense? — Nathan Pierson, Jan 02 '23 at 07:57
This question looks very similar to [this](https://stackoverflow.com/questions/70507742/how-can-i-reverse-my-linked-list-i-wrote-following-code-but-this-is-giving-onl?rq=1) one. — Ted Lyngmo, Jan 02 '23 at 08:00
This doesn't appear to me to have anything to do with `operator=`, so I've edited the question so that the title focuses on the actual problem. — Nathan Pierson, Jan 02 '23 at 08:00
That seems backwards to me. One of the major advantages linked lists have over other containers is that many operations on them can be done without invalidating references, and they can be used with otherwise-difficult types that are non-copyable and even non-movable (or at least not `noexcept` movable). And this is precisely because you can perform list operations like reversals and splices and so on just by changing where the nodes point, without needing to do anything to the underlying data. — Nathan Pierson, Jan 02 '23 at 08:37
The data in the linked list is `int`. It is cheaper to swap the values than to relink the nodes. I am talking about the example above. In reality I would do: `template void List::reverse() { const Node* oldHead = head; for (Node* nptr = head; ; nptr = nptr->previous) { std::swap(nptr->next, nptr->previous); if (nptr->previous == oldHead) // Previous was the original next break; } }` I published several examples here on SO already . . . — A M, Jan 02 '23 at 08:52
Nathan Pierson, I see the problem - i was trying to assign to nullptr, if I point ```temp``` back to head - the error is gone, however I just get the list before reversing. Also I tried using ```stack``` and just pushing ```data``` part in the stack (stl stack container) but then I can't read that back into my list — kanulilewa, Jan 02 '23 at 08:54

trincot · Accepted Answer · 2023-01-02T09:10:14.100

The problem is that temp will be nullptr by the time the second loop starts, and so temp->next is an invalid dereferencing.

Secondly, also head will have been assigned nullptr just before that second loop, and never gets anything else assigned.

There are many ways to solve this. One way is to just check what the value of temp is before dereferencing it, and use the opportunity to set head

So change the second loop body to this:

    while (!reversed.empty()) {
        if (temp) {
            temp = temp->next = reversed.top();
        } else {
            temp = head = reversed.top();
        }
        reversed.pop();
    }

Finally, note that there are more memory efficient ways to reverse a linked list. You can reverse the links without needing a stack.

Reversing a linked last causes "write access violation - temp was nullptr"

1 Answers1