Reverse a Linked List

Today we will discuss how to reverse a linked list. Proceed if you have basic knowledge of linked list otherwise you can read this post on where I have explained you about linked list. Let me explain you what a reversed linked list is. Suppose we have a linked list 1->2->3->4->5->NULL then the reverse of this list will be 5->4->3->2->1->NULL. So, let's discuss how we can reverse a linked list.

Procedure

1. First we will make a linked list.

2. Now we will traverse the linked list.

3. While traversing when we will reach the first node we will make it point NULL.

4. Then at each node we will make that node point to the previous node.

5. When we will reach the last node then we will update head and initialize it with the address of last node.

Code

#include<iostream>
using namespace std;
struct node
{
    int data;
    struct node* next;
};
struct node* head=NULL;

class linked
{
public:
    void insert(int x)
    {
        struct node* temp=new node();
        temp->data=x;
        temp->next=NULL;
        if(head==NULL)
        {
            head=temp;
        }
        else
        {
            struct node* temp1=head;
            while(temp1->next!=NULL)
            {
                temp1=temp1->next;
            }
            temp1->next =temp;
        }
    }

    void reverse()
    {
        struct node* current=head;
        struct node* prev=head;
        struct node* forward=head;
        forward=current->next;
        current->next=NULL;
        while(current!=NULL && forward!=NULL)
        {
            prev=current;
            current=forward;
            forward=forward->next;
            current->next=prev;
        }
        head=current;
    }


    void disp()
    {
        struct node* temp=head;
        while(temp!=NULL)
        {
            cout<<temp->data<<" ";
            temp=temp->next;
        }
        cout<<endl;
    }
};

int main()
{
    linked l;
    l.insert(1);
    l.insert(2);
    l.insert(3);
    l.insert(4);
    l.insert(5);
    l.insert(6);

    l.insert(9);
    l.disp();
    l.reverse();
    l.disp();
    return 0;
}

Explanation of Code( line by line)

1. First we will write a simple code of linked list which will have 2 functions:

- insert() - which will insert elements in the linked list.
- disp() - which will display the linked list.

2. Insert some values in the linked list.
3. Now we have created a function named reverse() to reverse the linked list.
4. In the reverse() function we have made 3 pointer to node variables:

prev : Which will point to the node previous to current node.
current : Which will point to the current node.
forward : Which will point to the node ahead of current node.

5. Initially prev, current and forward are initialized with head.

6. Then forward is initialized with the next node after current.

forward=current->next;

7. Then current->next is initialized to NULL because this current is the first node and after reversing the list it will become last node so it shall point to NULL.

8. Then we have started a loop to traverse the list till current!=NULL and forward!=NULL.

9.In the loop we have assigned prev with the address of current and current with the address of forward and forward with forward->next so that all 3 pointer to node can increment.

prev=current;
current=forward;

10. Then we have assigned the current->next with the address the prev because in order to reverse the linked list each node shall point to its previous node.

current->next=prev;

11. After while loop is over we have assigned head the address of current node because when the loop will be over current will be at last node and the last node will become the first node after reversing and first node is always pointed by head node.

Reverse a Linked List

Procedure

Code

Explanation of Code( line by line)

Contact Form