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..
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. Implemented in C++11
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node * next;
Node(int arg_data) : data(arg_data), next(NULL)
{}
};
class SingleLinkedList {
public:
SingleLinkedList()
{}
void Display(Node * head) {
Node * current = head;
while (current != NULL) {
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 == NULL or head->next == NULL)
return head;
Node * current = head;
Node * next_to_current = head->next;
head->next = NULL;
while(next_to_current != NULL) {
Node * temp = next_to_current->next;
next_to_current->next = current;
current = next_to_current;
next_to_current = temp;
}
return current;
}
};
int main() {
Node * head = new Node(2);
head->next = new Node(3);
head->next->next = new Node(5);
head->next->next->next = new Node(7);
head->next->next->next->next = new Node(11);
head->next->next->next->next->next = new 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);
delete head->next->next->next->next->next;
delete head->next->next->next->next;
delete head->next->next->next;
delete head->next->next;
delete head->next;
delete head;
return 0;
}
Output of reverse operation on a single linked list. Implemented in C++11
Single linked list :
2 3 5 7 11 13
Reversing the single linked list :
13 11 7 5 3 2