Reversing a linked list
Educative Answers TeamWhen 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
headstarts pointing to the last element of the list.
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 atNone, this node pointer points to the previous element so that thenextlink 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 tohead, the node being pointed to by this node pointer gets itsnextvariable set to thepreviousitem 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 thecurrentpointer 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
View all Courses
