Given a singly Linked List, we have to reverse the entire linked List in a Linear Time and we don’t have to use any extra auxiliary space.
Example:
3 --> 5 --> 7 --> 9 --> 11 --> NULL
Reversed List:11 --> 9 --> 7 --> 5 -->3 --> NULL
Read more about Linked List here…
Algorithm
- Create a new & temp list pointer and mark it NULL & old pointer will point to the head of the original list. Node *head=NULL, *temp = NULL;
- Let temp point the first node of the old list & move the old pointer to the next node. temp = old; old = old->next;
- Now make temp->next point to the new_list pointer and make new_list pointer point to the temp. temp->next = new_list; new_list = temp;
- Repeat step2 until the old pointer is not null or we have reached the end of the original list.
Node* Reverse_List(Node *old_list){
Node *new_list = NULL, *temp = NULL;
while(old_list != NULL){
temp = old_list;
old_list = old_list->next;
temp->next = new_list;
new_list = temp;
}
return new_list;
}
CPP implementation of the above algorithm
#include <bits/stdc++.h> using namespace std; class Node{ public: int value; Node *next; }; Node* Reverse_List(Node *old_list){ Node *new_list = NULL, *temp = NULL; while(old_list != NULL){ temp = old_list; old_list = old_list->next; temp->next = new_list; new_list = temp; } return new_list; } int main(){ Node *old_list=NULL, *current=NULL; //creating list for(int i=3;i<=11;i=i+2){ Node *temp = new Node; temp->value = i; temp->next = NULL; if(old_list==NULL){ current = temp; old_list = current; } else{ current->next = temp; current = current->next; } } //printing original list cout<<"Old List: "; current = old_list; while(current!=NULL){ cout<<current->value<<"->"; current = current->next; } cout<<"NULL"<<endl; Node *new_list = Reverse_List(old_list); //printing reversed list cout<<"New List: "; while(new_list!=NULL){ cout<<new_list->value<<"->"; new_list = new_list->next; } cout<<"NULL"<<endl; return 0; }
Output
Old List: 3->5->7->9->11->NULL
New List: 11->9->7->5->3->NULL
The time complexity of and algorithm to reverse a linked list in Linear time without using extra space is O(N), where N is the length of the Linked List.