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
struct LinkNode
{
    int data;
    struct LinkNode* next;
}

// Structure to represent the linked list
struct MyLinkedList
{
    struct LinkNode* head;
    struct LinkNode* tail;
}

// Function to create a new LinkNode with the given data
LinkNode* getLinkNode(int data)
{
    Create a new LinkNode with data
    Set the next pointer to NULL
    Return the new LinkNode
}

// Function to create a new MyLinkedList
MyLinkedList* getMyLinkedList()
{
    Create a new MyLinkedList
    Set the head and tail pointers to NULL
    Return the new MyLinkedList
}

// Function to add a new node at the end of the linked list
void insert(MyLinkedList* list, int data)
{
    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
LinkNode* reverse(MyLinkedList* list, LinkNode* node)
{
    // 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
    LinkNode* nextNode = reverse(list, node->next)
    
    // 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
void display(MyLinkedList* list)
{
    Set a temporary pointer to the head of the list
    If the temporary pointer is NULL
        Print "Empty linked list"
    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

  1. Start with an empty linked list (MyLinkedList) and add elements to it using the "insert" function.
  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.

Program List

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.

New Comment