Reverse A Linked List In C++

Tips On How To Reverse A Linked List In C++

Hello there everyone, in today’s tutorial we are going to discuss and implement how to reverse a linked list in C++ . Before we begin writing the program, let us understand in more depth about the Linked List data structure. Hence, we will thoroughly discuss what kind of data structure Linked List is and how to implement it. Many of us as a developer will face this data structure quite often and will solve it as well. You can use the VS Code Editor or any code editor of your choice to continue along with this tutorial.

What is a Linked List

Unlike an Array, a linked list is a linear data structure that does not contain the value in contiguous locations. Instead, the pointers connect the values and the elements of a linked list. A linked list has a series of connected values which we call Nodes. Each or say every element in the linked list includes a data node and an address to the next element. So the linked list elements are also popularly known as Nodes. Our approach to reverse a linked list in c++ will be very much simple and easy to understand.

Reverse A Linked List In C++

Now we have some knowledge about the Linked List data structure and how they form. In order to reverse a LinkedList in place, we need to reverse the pointers such that the next element now points to the previous element. Following are the input and output.

without reversing
after reversal

Reversing Linked List Using Iterative Approach

Now we will implement the linked list reversal technique with our iterative approach. In order to reverse the Linked List with an iterative method. First, we have to store the pointers for the next and previous elements. So that we do not lose our elements when we swap the memory address pointers to the next element in the LinkedList. The following image explains how we will reverse our Linked List by modifying the connections.

how it will be reversed

Following are the steps in this iterative approach on how to reverse a linked list in C++. First, we will have 3 instances named: Current, Next, and Previous. We will continue our loop until our Current becomes NULL.

  • Saving the next node of the current element to the next pointer.
  • Now set next to the current node to the previous pointer.
  • We will now set previous to current.
  • Shift the current element to next.

Finally, we must set the head to the last element we reached because the current has advanced one position past it. This is offered in the preceding node. Head to the previous position. As a result, the last member of the earlier LinkedList serves as our new Linked List’s head.

Implementation

// Iterative Approach
#include <iostream>
using namespace std;

/* Link list node */
struct Node {
	int data;
	struct Node* next;
	Node(int data)
	{
		this->data = data;
		next = NULL;
	}
};

struct LinkedList {
	Node* head;
	LinkedList() { head = NULL; }

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

		while (current != NULL) {
			// Store next
			next = current->next;
			// Reverse current node's pointer
			current->next = prev;
			// Move pointers one position ahead.
			prev = current;
			current = next;
		}
		head = prev;
	}

	/* Function to print linked list */
	void print()
	{
		struct Node* temp = head;
		while (temp != NULL) {
			cout << temp->data << " ";
			temp = temp->next;
		}
	}

	void push(int data)
	{
		Node* temp = new Node(data);
		temp->next = head;
		head = temp;
	}
};

/* Driver code*/
int main()
{
	/* Starting with the empty list */
	LinkedList ll;
	ll.push(20);
	ll.push(4);
	ll.push(15);
	ll.push(85);

	cout << "Given linked list\n";
	ll.print();

	ll.reverse();

	cout << "\nReversed Linked list \n";
	ll.print();
	return 0;
}
OUTPUT :
Given linked list
85 15 4 20 
Reversed Linked list 
20 4 15 85

Space-Time Complexity of Reversing a Linked List

Time Complexity – O(n)

Space Complexity – O(1)

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.