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 a linked list are as follows:
- Initialize resultant list as NULL.
- Traverse the complete list. While traversing the linked list, for every node encountered, remove that node, and add that node to the beginning of resultant list.
- At last, head of the resultant linked list will become the head of the original Linked List.
C++ Program to reverse a 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:
- Reverse a Linked List Using Stack.
- Printing Linked List in Reverse Order without actually reversing the Linked List.
- Swap Adjacent Elements of the Linked List.
- Count All Occurrences of a Particular Node in a Linked List.
- Bubble Sort on Linked List.
- Detect a Loop in a Linked List.
- Find the Length of the Loop present in the Linked List.
- Detect and Remove Loop from a Linked List.
- Segregate Even and Odd Nodes of the Linked List.
- Delete Complete Linked List.
- Delete Nth Node of the Linked List.
- Delete without head pointer of the Linked List.
- Delete All Occurrences of particular node of the Linked List.
- Delete Alternate Nodes of the Linked List.
- Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
- Remove Duplicate Nodes from an Unsorted Linked List.
- Remove Duplicate Nodes from a Sorted Linked List.
- Find Union and Intersection of Two Linked List.
- Merge Two Sorted Linked List.
- Insert a New Node at the Sorted Linked List.