I want to reverse a linked list but when i compile this code it terminates unexpectedly.

#include <bits/stdc  .h>
using namespace std;

class node{
public:
    int data;
    node* next;

    node(int val){
    data=val;
    next=NULL;
        }
};

For Inserting Elements in Linked List

void insertattail(node* &head,int lol){
    node* n= new node(lol);
    if(head==NULL){
        head=n;
        return;
    }
    node* temp=head;
    while(temp->next!=NULL){
        temp=temp->next;
    }
    temp->next=n;
}

Display Function to print linked list

void display(node* head){
    node* temp =head;
    do{
        cout<<temp->data<<"->";
        temp=temp->next;
    }
    while(temp!=NULL);
    cout<<"Null";

}

Function to reverse Linked List

node* reverseit(node* head){
    node* prevptr= NULL;
    node* currptr= head;
    node* nextptr= currptr->next;
    while(currptr!=NULL){
        currptr->next =prevptr;
        prevptr=currptr;
        currptr=nextptr;
        nextptr=currptr->next;
    }
    return prevptr;
}

Main Function

int main()
{
    node* head= NULL;
    insertattail(head,1);
    insertattail(head,2);
    insertattail(head,3);
    insertattail(head,8);
    node* newhead= reverseit(head);
    display(newhead);
    return 0;
}

I think the problem is in logic of reverse function. I just used the code for linked list and made small changes.

CodePudding user response：

Your initialization and 'incrementing' of nextptr both (potentially/eventually) dereference a NULL value of currptr. You should initialize nextptr to NULL and only change that to the 'real' next if currptr is not NULL; thus, its (re)assignment should be at the start of the loop, not at the end:

node* reverseit(node* head){
    node* prevptr = nullptr;
    node* currptr = head;
    node* nextptr = nullptr; // Don't assume a non-NULL currptr
    while (currptr != nullptr) {
        nextptr = currptr->next; // Safe here: save next
        currptr->next = prevptr; // Do the reversal here
        prevptr = currptr;       // Step forward through
        currptr = nextptr;       // the list (prev/curr)
    //  nextptr = currptr->next; // WRONG HERE: currptr will be NULL at some point
    }
    return prevptr;
}

CodePudding user response：

The function invokes undefined behavior.

For example let's at first assume that the list is empty. That is the pointer head is equal to nullptr. In this case using this line before the while loop within the function

node* nextptr= currptr->next;

accesses memory using a null pointer.

Or let's consider another example when current->next is equal to nullptr. In this case within the while loop these statements

    currptr=nextptr;
    nextptr=currptr->next;

again access memory using a null pointer.

And declarations of many pointers before the while loop

node* prevptr= NULL;
node* currptr= head;
node* nextptr= currptr->next;

makes the code less readable and clear.

The function can be defined the following way

node * reverseit( node *head )
{
    node *new_head = nullptr;

    for ( node *current = head; head != nullptr; head = current )
    {
        current = head->next;
        head->next = new_head;
        new_head = head;
    }

    return new_head;
}

If actually your program is a C program then instead of nullptr use NULL.

Also in main there is no need to introduce the new pointer newhead

node* newhead= reverseit(head);

You could just write

head = reverseit(head);

The function display can again invoke undefined behavior if the passed pointer to the head node is equal to nullptr. And the parameter of the function should have the qualifier const because within the function the list itself is not changed.

The function can be defined the following way

std::ostream & display( const node *head, std::ostream &os = std::cout )
{
    for ( const node *current = head; current != nullptr; current =current->next )
    {
        os << current->data << " -> ";
    }

    return os << "Null";
}

And the function can be called like

display( head ) << '\n';