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.