{"id":3639,"date":"2021-08-06T11:39:24","date_gmt":"2021-08-06T11:39:24","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=3639"},"modified":"2022-03-08T12:18:01","modified_gmt":"2022-03-08T12:18:01","slug":"recursively-reversing-a-linked-list-a-simple-implementation","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/recursively-reversing-a-linked-list-a-simple-implementation\/","title":{"rendered":"Recursively reversing a Linked List – A simple implementation"},"content":{"rendered":"

\"\"<\/p>\n

Introduction<\/h3>\n

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.<\/p>\n<\/p>\n

Problem Statement<\/h3>\n

In this question, we are given a singly linked list. We have to reverse the linked list, using recursion.<\/p>\n

Problem Statement Understanding<\/h3>\n

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.<\/p>\n

Input:<\/strong><\/p>\n

\"\"<\/p>\n

Output:<\/strong> <\/p>\n

\"\"<\/p>\n

Explanation:<\/strong> The given linked list has been reversed.<\/p>\n

This question is not a very complex one. We just have to reverse the given linked list. The only requirement is to use recursion. <\/p>\n

We should not think that recursion is tough. We will be doing almost the same operations that we would\u2019ve 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.<\/p>\n

Approach<\/h3>\n

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. <\/p>\n

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.<\/p>\n

Algorithm<\/h3>\n
    \n
  • Base Case – If the node is NULL, return NULL.<\/li>\n
  • 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.<\/li>\n
  • If the base cases fail, proceed further.<\/li>\n
  • Create a new node node1 and store the recurred value of node -> next in it.<\/li>\n
  • Now, as the recursive calls return values, make node1 -> next point to the current node.<\/li>\n
  • Make current node – > next point to NULL<\/li>\n
  • 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.<\/li>\n
  • In the end, return current node. <\/li>\n<\/ul>\n

    Dry Run<\/h3>\n

    \"\"<\/p>\n

    Code Implementation<\/h4>\n\t\t\t\t\t\t