Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

linked list
reverse
node

Reversing a linked list

Educative Answers Team

When given a singly linked list with an additional head pointer, implementing​ the reverse() method does the following:

  • All the links start pointing in the opposite direction.
  • The head starts pointing to the last element of the list.
svg viewer

Algorithm

Let’s have a look at an iterative approach of how to reverse a given linked list:

  • Initialize the following node pointers:
    • previous: Initially pointing at None, this node pointer points to the previous element so that the next link of the node can be reversed using it. This node pointer is then updated to the node next to it (i.e., current).

    • current: Initially pointing to head, the node being pointed to by this node pointer gets its next variable set to the previous item in the list. This node pointer is then updated to the node next to it (i.e., following).

    • following: Initially pointing to the second node, this node pointer​ is used so that the current pointer may move one step ahead in each iteration.

Implementation

The code tabs, below, implement the algorithm above.

#include <iostream> 
using namespace std; 

// Node implementation
struct Node {

	int data; 
	struct Node* next;

  //constructor 
	Node(int data) 
	{ 
		this->data = data; 
		this->next = NULL; 
	} 
}; 

struct LinkedList { 
	Node* head; 
  
  // Initialise head of the linked list
	LinkedList() 
	{ 
		head = NULL; 
	} 

	// Function to reverse the linked list
	void reverse() 
	{ 
		// Initialize current, previous and 
		// following pointers 
		Node* current = head; 
		Node *previous = NULL;
    Node* following = current->next; 

		while (current != NULL) { 
      // reverse the link
      current->next = previous;

      // move previous one step ahead
      previous = current;

      // move current one step ahead
      current = following;

      // move following to the next element if it exists
      if (following)
        following = following->next;
		} 
		head = previous; 
	} 

	// Print list
	void print() 
	{ 
		struct Node* temp = head;

		while (temp != NULL) { 
			cout << temp->data << " "; 
			temp = temp->next; 
		} 

    cout << endl;
	} 

  // function to insert element into the linked list
	void insert(int data) 
	{ 
		Node* temp = new Node(data); 
		temp->next = head; 
		head = temp; 
	} 
}; 

int main() 
{ 
	LinkedList ll; 
	ll.insert(4); 
	ll.insert(3); 
	ll.insert(2); 
	ll.insert(1); 

	cout << "Original linked list" << endl; 
	ll.print(); 

	ll.reverse(); 

	cout << "Reversed Linked list" << endl; 
	ll.print();

	return 0; 
} 

RELATED TAGS

linked list
reverse
node
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring