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

Read more about Linked List here

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.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promsie, we won't spam
Even we hate spam as much as you hate them

Books recommendation for interview preparation