Question

C++: Write a reverse function that receives a reference to a integer linked list and reverses the order of all the elements in it. For example, if the input linked list is 1 -> 4-> 2-> 3-> 6-> 5}, after processing by this function, the linked list should become 5-> 6-> 3-> 2-> 4-> 1. You need to write a main file to insert elements into the linked list and call the reverseLinkedList() function which takes the reference of first node of linked list and returns the reference of first node, after reversing the linked list. [User Input is not necessary]. Note: Do not use built in library function for linked list. You need to define your own linked list.

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks

#include<iostream>
using namespace std;

//a simple Node structure
struct Node{
        int data;
        Node* next;
};

//method to print the contents of a linked list, given first node
void print_list(Node *first){
        //looping through each node and printing data
        for(Node* n=first;n!=NULL;n=n->next){
                cout<<n->data;
                //printing -> if there is a next node
                if(n->next!=NULL){
                        cout<<" -> ";
                }
        }
        cout<<endl;
}

//method to insert a value at the end of a linked list pointed by first,
//and return the head of the list
Node* insert(Node* first, int data){
        //creating new node and setting data and next
        Node* n=new Node();
        n->data=data;
        n->next=NULL;
        //if first is NULL, returning n as new first
        if(first==NULL){
                return n;
        }else{
                //otherwise finding last node, and adding n as next of last
                Node* curr=first;
                while(curr->next!=NULL){
                        curr=curr->next;
                }
                curr->next=n;
                //returning first node
                return first;
        }
}

//required method to reverse a linked list
Node* reverseLinkedList(Node *node){
        //taking a reference to first node
    Node* curr=node;
    //initializing two Node* variables to NULL
    Node* prev=NULL;
    Node* next=NULL;
    //looping until curr is NULL
    while(curr!=NULL){
        //storing next of curr in next
        next=curr->next;
        //setting prev as new next node of prev
        curr->next=prev;
        //assigning curr to prev
        prev=curr;
        //and setting next as new curr
        curr=next;
        }
        //finally, returning prev as new first node
        return prev;
}

//main method for testing
int main(){
        //initializing an empty first node
        Node* first=NULL;
        //adding some numbers
        first=insert(first,1);
        first=insert(first,4);
        first=insert(first,2);
        first=insert(first,3);
        first=insert(first,6);
        first=insert(first,5);
        
        //printing list
        cout<<"List: ";
        print_list(first);
        
        //reversing
        first=reverseLinkedList(first);
        
        //printing list again
        cout<<"Reversed List: ";
        print_list(first);
        
        //before exiting, deleting memory of all nodes to prevent memory leaks.
        while(first!=NULL){
                Node* n=first;
                first=first->next;
                delete n;
        }
        return 0;
}

/*OUTPUT*/

List: 1 -> 4 -> 2 -> 3 -> 6 -> 5
Reversed List: 5 -> 6 -> 3 -> 2 -> 4 -> 1