Home Practice Programming Reverse a linked list in Linear Time without using extra space

# Reverse a linked list in Linear Time without using extra space

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
``````

Algorithm

1. 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;
2. Let temp point the first node of the old list & move the old pointer to the next node.                         temp = old; old = old->next;
3. 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;
4. 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.