Reverse a Linked List

Reverse a Linked List” is one of the favourite technical interview problem based on Linked List. Here, we are given a linked list and our task is to reverse the given list. 

NOTE: We need to reverse the order of the nodes, not reverse the data value of nodes.

The steps required to reverse the linked list is as follows:

  1. Initialize resultant list as NULL;
  2. Traverse the complete list. While traversing the list, for every node encountered, remove that node, and add that node to the beginning of resultant list.
  3. At last, head of the resultant linked list will become the head of the original Linked List.

C++ Program to reverse the linked list is as follows:

/* C++ Program to Reverse a Linked List */
#include<bits/stdc++.h>
using namespace std;

/* Strcuture of the Node of Linked List */
typedef struct node
{
    int data;
    struct node *next;
}Node;

/* Function to Insert Nodes in the Linked List */
void insert_end(Node **head, int ele)
{
    /* Creating a new node */
    Node *new_node;
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = ele;
    new_node->next = NULL;
    
    /* Check whether the linked list is empty or not */
    
    /* If Linked List is Empty */
    if(*head == NULL)     
    {
        *head = new_node;
        return;
    }
    
    /* 
       If Linked List is not empty, then traverse the complete linked list and
       pointer of last node of the linked list will point to the new node of 
       the Linked List.
    */
    Node *temp = NULL;
    temp = (*head);
    while(temp->next != NULL)
    temp=temp->next;
    temp->next = new_node;
}

/* Function to Reverse a Linked List */
Node *reverse(Node *head)
{
  Node *res = NULL;
  Node *temp = head;
  
  /* 
    Traverse the complete Linked List and remove nodes one-by-one from the linked List
    and add them at the beginning of the resultant linked list.
  */
  while(temp!=NULL)
  {
      Node *p = temp;
      temp = temp->next;
      p->next = NULL;
      p->next = res;
      res = p;
  }
  
  /* Head of resultant Linked List will become head of original linked list */
  head = res;
  return head;
}

/* Function to print the Linked List */
void print(Node *head)
{
    Node *temp = head;
    while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
    cout<<endl;
}
int main()
{
    Node *head;
    head = NULL;
    /* Insert Some Nodes in the Linked List */
    insert_end(&head,45);
    insert_end(&head,78);
    insert_end(&head,89);
    insert_end(&head,93);
    insert_end(&head,99);
    cout<<"Linked List Before Reversing:\n";
    print(head);
    /* Reverse a Linked List */
    head = reverse(head);
    cout<<"\nLinked List after Reversing:\n";
    print(head);
}
OUTPUT:
Linked List before Reversing:
45 78 89 93 99
Linked List after Reversing:
99 93 89 78 45

Related Posts:

  1. Reverse a Linked List Using Stack.
  2. Printing Linked List in Reverse Order without actually reversing the Linked List.
  3. Swap Adjacent Elements of the Linked List.
  4. Count All Occurrences of a Particular Node in a Linked List.
  5. Bubble Sort on Linked List.
  6. Detect a Loop in a Linked List.
  7. Find the Length of the Loop present in the Linked List.
  8. Detect and Remove Loop from a Linked List.
  9. Segregate Even and Odd Nodes of the Linked List.
  10. Delete Complete Linked List.
  11. Delete Nth Node of the Linked List.
  12. Delete without head pointer of the Linked List.
  13. Delete All Occurrences of particular node of the Linked List.
  14. Delete Alternate Nodes of the Linked List.
  15. Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
  16. Remove Duplicate Nodes from an Unsorted Linked List.
  17. Remove Duplicate Nodes from a Sorted Linked List.
  18. Find Union and Intersection of Two Linked List.
  19. Merge Two Sorted Linked List.
  20. Insert a New Node at the Sorted Linked List.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *