Posted on by Kalkicode
Code Recursion

# Reverse linked list using recursion

In the context of linked lists, a reversal operation involves changing the direction of the pointers in each node, so that the last node becomes the new head of the list, and the previous head becomes the new tail. This transformation effectively "reverses" the order of elements in the list.

## Problem Statement

The problem is to reverse a given singly linked list using recursion. Given a linked list, we need to write a recursive function to reverse the order of the nodes in the list and update the head and tail pointers accordingly.

## Explanation with Suitable Example

Let's consider the following linked list as an example: 1 -> 4 -> 3 -> 7 -> 8

We start with the head node containing data 1 and the tail node containing data 8. To reverse the list, we need to change the pointers as follows:

1. 1 -> 4 -> 3 -> 7 -> 8 (Original list)
2. 1 <- 4 -> 3 -> 7 -> 8
3. 1 <- 4 <- 3 -> 7 -> 8
4. 1 <- 4 <- 3 <- 7 -> 8
5. 1 <- 4 <- 3 <- 7 <- 8

After the reversal, the new head will be the node containing data 8, and the new tail will be the node containing data 1. The reversed linked list will be: 8 -> 7 -> 3 -> 4 -> 1

## Pseudocode

``````// Structure to define a single node in the linked list
{
int data;
}

// Structure to represent the linked list
{
}

// Function to create a new LinkNode with the given data
{
Create a new LinkNode with data
Set the next pointer to NULL
}

// Function to create a new MyLinkedList
{
Set the head and tail pointers to NULL
}

// Function to add a new node at the end of the linked list
{
Create a new LinkNode with data
If the list is empty (head is NULL)
Set the head and tail pointers to the new node
Else
Set the next pointer of the current tail node to the new node
Update the tail pointer to the new node
}

// Function to reverse the linked list using recursion
{
// Base case: if the current node is NULL, return NULL
If the node is NULL
Return NULL

// Recursively call the reverse function on the next node

// If the current node is the tail node
If the node is equal to the tail node of the list
Update the head pointer of the list to the current node

// For other nodes
Else
Set the next pointer of the next node to the current node

// Unlink the current node from the next node
Set the next pointer of the current node to NULL

// Return the current node (it becomes the new tail in the reversed list)
Return the current node
}

// Function to display the elements of the linked list
{
Set a temporary pointer to the head of the list
If the temporary pointer is NULL
While the temporary pointer is not NULL
Print the data of the current node
Move the temporary pointer to the next node
}
``````
1. The main function will initialize the linked list and add elements (1, 4, 3, 7, 8) to it using the "insert" function.
2. The "display" function will be used to print the elements of the linked list before and after reversal.
3. The "reverse" function will be a recursive function that takes the linked list and the current node as input and returns the last node of the reversed list.
4. The base case of the recursion is when the current node is NULL, in which case we return NULL.
5. Otherwise, we recursively call the "reverse" function with the next node.
6. Once we reach the last node (tail), we update the head of the linked list to be the current node.
7. For other nodes, we update the "next" pointer of the current node to point to the previous node in the reversed list.
8. Finally, we set the "next" pointer of the current node to NULL and return the current node.

## Algorithm Explanation

2. Display the original linked list using the "display" function.
3. Call the "reverse" function with the linked list and its head node as parameters.
4. The "reverse" function is a recursive function that takes a linked list and a current node as input.
5. If the current node is NULL, return NULL as the base case of the recursion.
6. Otherwise, recursively call the "reverse" function with the next node and store the returned value in "nextNode."
7. If the current node is the tail (last node) of the original list, update the head of the linked list to be the current node.
8. For other nodes, update the "next" pointer of the current node to point to the previous node in the reversed list, i.e., "nextNode."
9. Unlink the current node by setting its "next" pointer to NULL.
10. Return the current node.
11. After the "reverse" function call, the head of the linked list will now point to the last node (new head) of the reversed list.
12. Display the reversed linked list using the "display" function.

## Resultant Output Explanation

The original linked list is: 1 -> 4 -> 3 -> 7 -> 8 The reversed linked list is: 8 -> 7 -> 3 -> 4 -> 1

The output after executing the program will be as follows:

```Before Reverse : 1 4 3 7 8
After Reverse : 8 7 3 4 1```

## Time Complexity

The time complexity of reversing a linked list using recursion is O(N), where N is the number of nodes in the linked list. This is because the recursion involves visiting each node exactly once during the reversal process. The space complexity is O(N) as well, as the recursion uses the call stack, and in the worst case, the stack depth will be equal to the number of nodes in the linked list.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post