Reversing a singly linked list
Idea to reverse a singly linked list is a below.
a) If there is just a one node in a singly linked list, we return it as it is as there aren’t any links to be reversed.
b) If there are more than one nodes in a singly linked list, we do the following..
- Start with the Head node and use two additional nodes current_node and next_to_current.
current_node stores the address of Head node.
next_to_current stores the address of Head’s next node.
- Point Head’s next to Null.
- Store the address of the node next to next_to_current into a temp node before reversing the link of next_to_current.
- Point next_to_current to current thus reversing the links between them.
- current takes the place of next_to_current & next_to_current takes place of temp as the reversal of the links happen between every pair of adjacent nodes.
- Repeat the link reversal steps between current and next_to_current till next_to_current points to null indicating the end of the list.
- Thus we have the Reversed Singly linked list.
Time Complexity : O ( N ), where N is the number of nodes in the linked list. Space Complexity : O ( N ), where N is the number of nodes in the linked list.
C++ program to reverse a singly linked list.
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node * next;
Node (int arg_data) : data (arg_data), next (nullptr)
{}
};
class SingleLinkedList {
public:
SingleLinkedList()
{}
void Display (Node * head) {
Node * current = head;
while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
}
Node * Reverse (Node * head) {
// If head is null or only head (i.e single node), return head.
if (head == nullptr || head->next == nullptr)
return head;
Node * current = head;
Node * next_to_current = head->next;
head->next = nullptr;
while (next_to_current != nullptr) {
Node * temp = next_to_current->next;
next_to_current->next = current;
current = next_to_current;
next_to_current = temp;
}
return current;
}
// Free the linked list
void Free (Node *head) {
while (head != nullptr) {
Node * temp = head->next;
head->next = nullptr;
delete head;
head = temp;
}
}
};
int main() {
Node * head = new Node(2);
Node * node_3 = new Node(3);
Node * node_5 = new Node(5);
Node * node_7 = new Node(7);
Node * node_11 = new Node(11);
Node * node_13 = new Node(13);
head->next = node_3;
node_3->next = node_5;
node_5->next = node_7;
node_7->next = node_11;
node_11->next = node_13;
SingleLinkedList s;
cout <<"\nSingle linked list : " << endl;
s.Display(head);
cout <<"\nReversing the single linked list : " << endl;
head = s.Reverse(head);
s.Display(head);
cout <<"\nFreeing the single linked list." << endl;
s.Free(head);
return 0;
}
Output
Single linked list :
2 3 5 7 11 13
Reversing the single linked list :
13 11 7 5 3 2
Freeing the single linked list.