Home Programming Puzzles 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

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.

Subscribe to our weekly newsletter

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

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

LEAVE A REPLY

Please enter your comment!
Please enter your name here