Given pointer to the head node of a linked list, the task is to recursively reverse the linked list. We need to reverse the list by changing 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->NULL
Input : Head of following linked list
1->2->3->4->5->NULL
Output : Linked list should be changed to,
5->4->3->2->1->NULL
Input : NULL
Output : NULL
Input : 1->NULL
Output : 1->NULL
We have discussed an iterative and two recursive approaches in previous post on reverse a linked list. In this approach of reversing a linked list by passing a single pointer what we are trying to do is that we are making the previous node of the current node as his next node to reverse the linked list.
- We return the pointer of next node to his previous(current) node and then make the previous node as the next node of returned node and then return the current node.
- We first traverse to the last node and make the last node the head node of reversed linked list and then apply the above procedure in a recursive manner.
Implementation:
C++
// 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; } /* Function to reverse the linked list */ Node* reverse(Node* node) { if (node == NULL) return NULL; if (node->next == NULL) { head = node; return node; } Node* node1 = reverse(node->next); node1->next = node; node->next = NULL; return node; } /* 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.reverse(ll.head); cout << "\nReversed Linked list \n"; ll.print(); return 0;} |
Java
// Recursive Java program to reverse// a linked listimport java.io.BufferedWriter;import java.io.IOException;import java.io.OutputStreamWriter;import java.util.Scanner;public class ReverseLinkedListRecursive { /* Link list node */ static class Node { public int data; public Node next; public Node(int nodeData) { this.data = nodeData; this.next = null; } } static class LinkedList { public Node head; public LinkedList() { this.head = null; } public void insertNode(int nodeData) { Node node = new Node(nodeData); if (this.head != null) { node.next = head; } this.head = node; } } /* Function to print linked list */ public static void printSinglyLinkedList(Node node, String sep) throws IOException { while (node != null) { System.out.print(String.valueOf(node.data) + sep); node = node.next; } } // Complete the reverse function below. static Node reverse(Node head) { if(head == null) { return head; } // last node or only one node if(head.next == null) { return head; } Node newHeadNode = reverse(head.next); // change references for middle chain head.next.next = head; head.next = null; // send back new head node in every recursion return newHeadNode; } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) throws IOException { LinkedList llist = new LinkedList(); llist.insertNode(20); llist.insertNode(4); llist.insertNode(15); llist.insertNode(85); System.out.println("Given linked list:"); printSinglyLinkedList(llist.head, " "); System.out.println(); System.out.println("Reversed Linked list:"); Node llist1 = reverse(llist.head); printSinglyLinkedList(llist1, " "); scanner.close(); }} |
Python3
# Recursive Python3 program to reverse# a linked listimport math# Link list node class Node: def __init__(self, data): self.data = data self.next = None def LinkedList(): head = None # Function to reverse the linked list def reverse(node): if (node == None): return node if (node.next == None): return node node1 = reverse(node.next) node.next.next = node node.next = None return node1# Function to print linked list def printList(): temp = head while (temp != None) : print(temp.data, end = " ") temp = temp.next def push(head_ref, new_data): new_node = Node(new_data) new_node.data = new_data new_node.next = head_ref head_ref = new_node return head_ref# Driver Codeif __name__=='__main__': # Start with the empty list head = LinkedList() head = push(head, 20) head = push(head, 4) head = push(head, 15) head = push(head, 85) print("Given linked list") printList() head = reverse(head) print("\nReversed Linked list") printList() # This code is contributed by AbhiThakur |
C#
// Recursive C# program to reverse// a linked listusing System;public class ReverseLinkedListRecursive { /* Link list node */ public class Node { public int data; public Node next; public Node(int nodeData) { this.data = nodeData; this.next = null; } } class LinkedList { public Node head; public LinkedList() { this.head = null; } public void insertNode(int nodeData) { Node node = new Node(nodeData); if (this.head != null) { node.next = head; } this.head = node; } } /* Function to print linked list */ public static void printSinglyLinkedList(Node node, String sep) { while (node != null) { Console.Write(node.data + sep); node = node.next; } } // Complete the reverse function below. static Node reverse(Node head) { if(head == null) { return head; } // last node or only one node if(head.next == null) { return head; } Node newHeadNode = reverse(head.next); // change references for middle chain head.next.next = head; head.next = null; // send back new head // node in every recursion return newHeadNode; } // Driver code public static void Main(String[] args) { LinkedList llist = new LinkedList(); llist.insertNode(20); llist.insertNode(4); llist.insertNode(15); llist.insertNode(85); Console.WriteLine("Given linked list:"); printSinglyLinkedList(llist.head, " "); Console.WriteLine(); Console.WriteLine("Reversed Linked list:"); Node llist1 = reverse(llist.head); printSinglyLinkedList(llist1, " "); }}// This code has been contributed by Rajput-Ji |
Javascript
// Recursive JavaScript program to reverse// a linked list// Link List nodeclass Node{ constructor(data){ this.data = data; this.next = null; }}let head = null;// Function to reverse the linked listfunction reverse(node){ if(node == null) return null; if(node.next == null){ head = node; return node; } let node1 = reverse(node.next); node1.next = node; node.next = null; return node;}// Function to print linked listfunction print(){ let temp = head; while(temp != null){ console.log(temp.data + " "); temp = temp.next; }}function push(data){ let temp = new Node(data); temp.next = head; head = temp;}// Driver Codepush(20);push(4);push(15);push(85);console.log("Given Linked List ");print();reverse(head)console.log("\nReversed Linked List");print();// This code is contributed by Yash Agarwal(yashagarwal2852002) |
Output
Given linked list 85 15 4 20 Reversed Linked list 20 4 15 85
Time Complexity: O(N) where N is the number of elements in the linked list.
Auxiliary Space: O(N) due to stack recursion call.
Reverse a linked list by Tail Recursive Method:
Follow the steps below to solve the problem:
1) First update next with next node of current i.e. next = current->next
2) Now make a reverse link from current node to previous node i.e. curr->next = prev
3) If the visited node is the last node then just make a reverse link from the current node to previous node and update head.
Below is the implementation of the above approach:
C++
// A simple and tail recursive C++ program to reverse// a linked list#include <bits/stdc++.h>using namespace std;struct Node { int data; struct Node* next; Node(int data){ this->data = data; this->next = NULL; }};// A simple and tail-recursive function to reverse// a linked list. prev is passed as NULL initially.void reverseUtil(Node* curr, Node* prev, Node** head){ /* If last node mark it head*/ if (!curr->next) { *head = curr; /* Update next to prev node */ curr->next = prev; return; } /* Save curr->next node for recursive call */ Node* next = curr->next; /* and update next ..*/ curr->next = prev; reverseUtil(next, curr, head);}// This function mainly calls reverseUtil()// with prev as NULLvoid reverse(Node** head){ if (!head) return; reverseUtil(*head, NULL, head);}// A utility function to print a linked listvoid printlist(Node* head){ while (head != NULL) { cout << head->data << " "; head = head->next; }}// Driver code to test above functionint main(){ Node* head1 = new Node(1); head1->next = new Node(2); head1->next->next = new Node(3); head1->next->next->next = new Node(4); head1->next->next->next->next = new Node(5); head1->next->next->next->next->next = new Node(6); head1->next->next->next->next->next->next = new Node(7); head1->next->next->next->next->next->next->next= new Node(8); cout << "Given linked list\n"; printlist(head1); cout<<endl; reverse(&head1); cout << "Reversed linked list\n"; printlist(head1); return 0;}// This code is contributed by Kirti Agarwal |
Java
// A simple and tail recursive Java program to reverse// a linked listimport java.io.*;import java.util.*;// Linked List Node classclass Node { int data; Node next; Node(int data) { this.data = data; this.next = null; }}// Linked List classclass LinkedList { Node head; // A simple and tail-recursive function to reverse // a linked list. prev is passed as null initially. void reverseUtil(Node curr, Node prev) { /* If last node mark it head*/ if (curr.next == null) { head = curr; /* Update next to prev node */ curr.next = prev; return; } /* Save curr.next node for recursive call */ Node next = curr.next; /* and update next ..*/ curr.next = prev; reverseUtil(next, curr); } // This function mainly calls reverseUtil() // with prev as null void reverse() { if (head == null) return; reverseUtil(head, null); } // A utility function to print a linked list void printList() { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } }}// Driver code to test above functionclass Main { public static void main(String args[]) { LinkedList list = new LinkedList(); list.head = new Node(1); list.head.next = new Node(2); list.head.next.next = new Node(3); list.head.next.next.next = new Node(4); list.head.next.next.next.next = new Node(5); list.head.next.next.next.next.next = new Node(6); list.head.next.next.next.next.next.next = new Node(7); list.head.next.next.next.next.next.next.next = new Node(8); System.out.println("Given linked list"); list.printList(); System.out.println(); list.reverse(); System.out.println("Reversed linked list"); list.printList(); }} |
Python3
# A simple and tail recursive Python program to reverse# a linked listclass Node: def __init__(self, data): self.data = data self.next = None head1 = None# a simple and tail-reverse function to reverse# a linked list. prev is passed as null initially.def reverseUtil(curr, prev): # if last node mark it head if(curr.next is None): global head1 head1 = curr # update next to prev node curr.next = prev return # save curr.next node from recursive call next = curr.next curr.next = prev reverseUtil(next, curr) # this function mainly calls reverseUtil()# with prev as nulldef reverse(): global head1 if(head1 is None): return reverseUtil(head1, None) # utility function to print a linked listdef printlist(head): while(head is not None): print(head.data , end = " ") head = head.next print("")# driver program to test above functionhead1 = Node(1)head1.next = Node(2)head1.next.next = Node(3)head1.next.next.next = Node(4)head1.next.next.next.next = Node(5)head1.next.next.next.next.next = Node(6)head1.next.next.next.next.next.next = Node(7)head1.next.next.next.next.next.next.next= Node(8) print("Given Linked List : ")printlist(head1)reverse()print("Reversed Linked List : ")printlist(head1) |
C#
using System;// A simple C# program to represent a node in a linked listpublic class Node { public int data; public Node next; public Node(int data) { this.data = data; this.next = null; }}public class LinkedList { public static Node head1 = null; // A simple and tail-recursive function to reverse a linked list // prev is passed as null initially. public static void reverseUtil(Node curr, Node prev) { // If last node, mark it as head if (curr.next == null) { head1 = curr; // Update next to prev node curr.next = prev; return; } // Save curr.next node from recursive call Node next = curr.next; curr.next = prev; reverseUtil(next, curr); } // This function mainly calls reverseUtil() with prev as null public static void reverse() { if (head1 == null) { return; } reverseUtil(head1, null); } // Utility function to print a linked list public static void printlist(Node head) { while (head != null) { Console.Write(head.data + " "); head = head.next; } Console.WriteLine(); } // Driver code to test above functions public static void Main() { head1 = new Node(1); head1.next = new Node(2); head1.next.next = new Node(3); head1.next.next.next = new Node(4); head1.next.next.next.next = new Node(5); head1.next.next.next.next.next = new Node(6); head1.next.next.next.next.next.next = new Node(7); head1.next.next.next.next.next.next.next = new Node(8); Console.Write("Given Linked List : "); printlist(head1); reverse(); Console.Write("Reversed Linked List : "); printlist(head1); }} |
Javascript
// A simple and tail recursive C++ Program to reverse// a linked listclass Node{ constructor(data){ this.data = data; this.next = null; }}let head1 = null;// A simple and tail-recursive function to reverse// a linked list. prev is passed as NULL initially.function reverseUtil(curr, prev){ // if last node mark it head if(!curr.next){ head1 = curr; // update next to prev node curr.next = prev; return; } // save curr.next node fro recursive call let next = curr.next; curr.next = prev; reverseUtil(next, curr);}// this function mainly calls reverseUtil()// with prev as nullfunction reverse(){ if(head1 == null) return; reverseUtil(head1, null);}// a utility function to print a linked listfunction printlist(head){ while(head != null){ console.log(head.data + " "); head = head.next; }}// driver code to test above functionhead1 = new Node(1);head1.next = new Node(2);head1.next.next = new Node(3);head1.next.next.next = new Node(4);head1.next.next.next.next = new Node(5);head1.next.next.next.next.next = new Node(6);head1.next.next.next.next.next.next = new Node(7);head1.next.next.next.next.next.next.next= new Node(8);console.log("Given Linked List : ");printlist(head1);reverse();console.log("Reversed Linked List : ");printlist(head1); |
Output
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) where N is the number of elements in the linked list.
Auxiliary Space: O(N) due to stack recursion call.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
