Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing the links between nodes.
Examples:
Input: Head of following linked list
1->2->3->4->NULL
Output: Linked list should be changed to,
4->3->2->1->NULLInput: Head of following linked list
1->2->3->4->5->NULL
Output: Linked list should be changed to,
5->4->3->2->1->NULLInput: NULL
Output: NULLInput: 1->NULL
Output: 1->NULL
Iterative Method
- Initialize three pointers prev as NULL, curr as head and next as NULL.
- Iterate through the linked list. In loop, do following.
// Before changing next of current,
// store next node
next = curr->next
// Now change next of current
// This is where actual reversing happens
curr->next = prev
// Move prev and curr one step forward
prev = curr
curr = next

Below is the implementation of the above approach:
Output:
Given linked list 85 15 4 20 Reversed Linked list 20 4 15 85
Time Complexity: O(n)
Auxiliary Space: O(1)
Recursive Method:
1) Divide the list in two parts - first node and
rest of the linked list.
2) Call reverse for the rest of the linked list.
3) Link rest to first.
4) Fix head pointer
// Recursive C++ program to reverse// a linked list#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; } Node* reverse(Node* head) { if (head == NULL || head->next == NULL) return head; /* reverse the rest list and put the first element at the end */ Node* rest = reverse(head->next); head->next->next = head; /* tricky step -- see the diagram */ head->next = NULL; /* fix the head pointer */ return rest; } /* 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 program to test above function*/int main(){ /* Start 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.head = ll.reverse(ll.head); cout << "\nReversed Linked list \n"; ll.print(); return 0;} |
Output:
Given linked list 85 15 4 20 Reversed Linked list 20 4 15 85
Time Complexity: O(n)
Auxiliary Space: O(n)
A Simpler and Tail Recursive Method
Below is the implementation of this method.
Given linked list 1 2 3 4 5 6 7 8 Reversed linked list 8 7 6 5 4 3 2 1
Time Complexity: O(N)
As we do certain operation for every node of the linked list.
Auxiliary Space: O(1)
As constant extra space is used.
Head Recursive Method:
// Head recursive C++ program to reverse a linked list#include <iostream>using namespace std;// Linked list nodeclass Node {public: int data; Node* next; // constructor: automatically assigns the value to the // data and next pointer to NULL Node(){}; Node(int val) : data(val) , next(NULL){};};void reverseUtil(Node* curr, Node* prev, Node** headref){ // Base Case - If curr is last node if (curr->next == NULL) { // Update head of the linked list *headref = curr; // Update next to prev node curr->next = prev; return; } // Recursive Call for next node reverseUtil(curr->next, curr, headref); // Update next to prev node curr->next = prev;}void reverse(Node** headref){ // If linked list is empty or contains single node if (*headref == NULL || (*headref)->next == NULL) return; // Call reverseUtil() with prev as NULL reverseUtil(*headref, NULL, headref);}// Function to insert a node at the end of linked listvoid push(Node** headref, int x){ Node* newptr = new Node(x); if (*headref == NULL) { *headref = newptr; } else { Node* temp = *headref; while (temp->next != NULL) { temp = temp->next; } temp->next = newptr; }}// Functio to print the linked listvoid print(Node* headref){ while (headref != NULL) { cout << headref->data << " "; headref = headref->next; } cout << "\n";}int main(){ Node* head = NULL; // head->1->2->3->4->5->6->NULL push(&head, 1); push(&head, 2); push(&head, 3); push(&head, 4); push(&head, 5); push(&head, 6); cout << "Given Linked List\n"; print(head); reverse(&head); cout << "Reversed Linked List\n"; print(head); return 0;}//This code is contributed by Anisha Wagh |
Output:
Given Linked List 1 2 3 4 5 6 Reversed Linked List 6 5 4 3 2 1
Time Complexity : O(N)
Auxiliary Space: O(N) for call stack
Using Stack:
Algorithm –
- Store the nodes(values and address) in the stack until all the values are entered.
- Once all entries are done, Update the Head pointer to the last location(i.e the last value).
- Start popping the nodes(value and address) and store them in the same order until the stack is empty.
- Update the next pointer of last Node in the stack by NULL.
Below is the implementation of the above approach:
// C++ program for above approach#include <bits/stdc++.h>#include <iostream>using namespace std;// Create a class Node to enter values and address in the listclass Node {public: int data; Node* next;};// Function to reverse the linked listvoid reverseLL(Node** head){ // Create a stack "s" of Node type stack<Node*> s; Node* temp = *head; while (temp->next != NULL) { // Push all the nodes in to stack s.push(temp); temp = temp->next; } *head = temp; while (!s.empty()) { // Store the top value of stack in list temp->next = s.top(); // Pop the value from stack s.pop(); // update the next pointer in the list temp = temp->next; } temp->next = NULL;}// Function to Display the elements in Listvoid printlist(Node* temp){ while (temp != NULL) { cout << temp->data << " "; temp = temp->next; }}// Program to insert back of the linked listvoid insert_back(Node** head, int value){ // we have used insertion at back method to enter values // in the list.(eg: head->1->2->3->4->Null) Node* temp = new Node(); temp->data = value; temp->next = NULL; // If *head equals to NULL if (*head == NULL) { *head = temp; return; } else { Node* last_node = *head; while (last_node->next != NULL) last_node = last_node->next; last_node->next = temp; return; }}// Driver Codeint main(){ Node* head = NULL; insert_back(&head, 1); insert_back(&head, 2); insert_back(&head, 3); insert_back(&head, 4); cout << "Given linked list\n"; printlist(head); reverseLL(&head); cout << "\nReversed linked list\n"; printlist(head); return 0;}// This code is contributed by Aditya Kumar (adityakumar129) |
Given linked list 1 2 3 4 Reversed linked list 4 3 2 1
Thanks to Gaurav Ahirwar for suggesting this solution.
Time Complexity: O(N)
As we do certain operation for every node of the linked list.
Auxiliary Space: O(N)
Space is used to store the nodes in the stack.
Using array:
Algorithm :-
1. Create a linked list.
2. Count the number of nodes present in the Linked List
3. Initialize an array with the size of the count.
4. Store the elements of the Linked list in array
5. Print the array from the last index to the first.
Input : 1->2->3->4->5 Output: 5->4->3->2->1
Time complexity: O(N) as we visit every node once.
Auxiliary Space: O(N) as extra space is used to store all the nodes in the array.
No comments:
Post a Comment