Last Updated on March 8, 2022 by Ria Pathak
Introduction
The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.
Problem Statement
In this question, we are given a singly linked list. We have to reverse the linked list, using recursion.
Problem Statement Understanding
Let the given linked list be 1 -> 2 -> 3 -> 4. Now, with the help of recursion, we have to reverse the linked list. The reverse linked list is 4 -> 3 -> 2 -> 1.
Input:
Output:
Explanation: The given linked list has been reversed.
This question is not a very complex one. We just have to reverse the given linked list. The only requirement is to use recursion.
We should not think that recursion is tough. We will be doing almost the same operations that we would’ve done with a loop. The only addition will be that we will keep recurring until we hit the base case. Let us have a glance at the approach.
Approach
The approach is going to be pretty simple. We are going to traverse through the list and make the previous node of the current node as its next node. After this, we are going to recur for the next node.
When we reach the last node, we will make it the head of our new linked list, and then recursively the other nodes will get added to our new linked list one by one.
Algorithm
- Base Case – If the node is NULL, return NULL.
- Another Base Case – If node – > next is NULL, we will make the node the head of the new linked list, as it is the last node of the list.
- If the base cases fail, proceed further.
- Create a new node node1 and store the recurred value of node -> next in it.
- Now, as the recursive calls return values, make node1 -> next point to the current node.
- Make current node – > next point to NULL
- By doing the above steps, we are changing the links of every node, i.e. we are making the current node point to its previous node.
- In the end, return current node.
Dry Run
Code Implementation
#include <stdio.h>
#include <stdlib.h>
// A Linked List Node
struct Node
{
int data;
struct Node* next;
};
// Helper function to print a given linked list
void printList(struct Node* head)
{
struct Node* ptr = head;
while (ptr)
{
printf("%d —> ", ptr->data);
ptr = ptr->next;
}
printf("NULL\n");
}
// Helper function to insert a new node at the beginning of the linked list
void push(struct Node** head, int data)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = *head;
*head = newNode;
}
// Recursive function to reverse a given linked list. It reverses the
// given linked list by fixing the head pointer and then `.next`
// pointers of every node in reverse order
void recursiveReverse(struct Node* head, struct Node** headRef)
{
struct Node* first;
struct Node* rest;
// empty list base case
if (head == NULL) {
return;
}
first = head; // suppose first = {1, 2, 3}
rest = first->next; // rest = {2, 3}
// base case: the list has only one node
if (rest == NULL)
{
// fix the head pointer here
*headRef = first;
return;
}
// recursively reverse the smaller {2, 3} case
// after: rest = {3, 2}
recursiveReverse(rest, headRef);
// put the first item at the end of the list
rest->next = first;
first->next = NULL; // (tricky step — make a drawing)
}
// Reverse a given linked list. The function takes a pointer
// (reference) to the head pointer
void reverse(struct Node** head) {
recursiveReverse(*head, head);
}
int main()
{
struct Node* head = NULL;
// create linked list 10->12->8->4->6
push(&head, 16);
push(&head, 14);
push(&head, 80);
push(&head, 12);
push(&head, 20);
reverse(&head);
printList(head);
return 0;
}
#include <iostream>
using namespace std;
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 list
Node* reverse(Node* node)
{
if (node == NULL)
return NULL;
// if current node is the last node
if (node->next == NULL) {
head = node;
return node;
}
// recur for the next node
Node* node1 = reverse(node->next);
// Change the links accordingly
node1->next = node;
node->next = NULL;
return node;
}
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;
}
};
int main()
{
LinkedList ll;
ll.push(4);
ll.push(3);
ll.push(2);
ll.push(1);
cout << "Given linked list\n";
ll.print();
ll.reverse(ll.head);
cout << "\nReversed Linked list \n";
ll.print();
return 0;
}
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;
public class ReverseLinkedListRecursive {
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;
}
}
public static void printSinglyLinkedList(Node node,
String sep) throws IOException {
while (node != null) {
System.out.print(String.valueOf(node.data) + sep);
node = node.next;
}
}
static Node reverse(Node head) {
if(head == null) {
return head;
}
if(head.next == null) {
return head;
}
Node newHeadNode = reverse(head.next);
head.next.next = head;
head.next = null;
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(4);
llist.insertNode(3);
llist.insertNode(2);
llist.insertNode(1);
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();
}
}
class Node:
def __init__(self, data):
self.data = data
self.next = None
def LinkedList():
head = None
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
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
if __name__=='__main__':
head = LinkedList()
head = push(head, 4)
head = push(head, 3)
head = push(head, 2)
head = push(head, 1)
print("Given linked list")
printList()
head = reverse(head)
print("\nReversed Linked list")
printList()
Output
Given linked list
1 2 3 4
Reversed Linked list
4 3 2 1
[forminator_quiz id=”3640″]
Space Complexity: O(n), space required for recursion stack.
So, in this article, we have tried to explain the most efficient approach to recursively reverse a linked list. This is an important question when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.