Reverse LinkedList Using Recursion: A Comprehensive Guide and Code Example

Reversing a linked list using recursion is a fundamental and interesting problem in computer science. It not only helps in understanding the underlying data structure but also showcases the power of recursion. This guide will walk you through the process of reversing a linked list in C using recursion, step by step, and provide a detailed explanation of the code.

Step-by-Step Explanation

Reversing a linked list using recursion involves changing the direction of the next pointers in each node. Here is a step-by-step guide to achieving this:

1. Define the Node Structure

The first step is to define the structure for a linked list node. Each node should have a data value and a pointer to the next node.

struct Node {    int data;    Node *next;    Node(int val, Node *next  nullptr) : data(val), next(next) {}};

2. Recursive Function

To reverse the linked list, write a recursive function that:

First checks if the list is empty or has only one node (base case). If so, simply return the node as reversing a single node or empty list doesn’t change anything.

Otherwise, the function moves to the next node and calls itself recursively until it reaches the end.

Once it reaches the last node, it sets the next pointer of the following node to point back to the current node, effectively reversing the link.

Finally, it sets the next pointer of the current node to nullptr, marking the end of the reversed list.

Node* reverseRecursive(Node* head) {    // Base case: if the list is empty or only one node, return head    if (!head || !head-next) {        return head;    }    // Recursively reverse the remaining list    Node* newHead  reverseRecursive(head-next);    // Change the next nodes next pointer to point back to current node    head-next-next  head;    // Set the current nodes next pointer to nullptr    head-next  nullptr;    // Return the new head of the reversed list    return newHead;}

3. Update the Head

The head of the list should be updated to the last node after reversing.

Code Example

The following code demonstrates the above steps with a complete example in C .

#include iostreamusing namespace std;// Define the structure of a linked list nodestruct Node {    int data;    Node* next;    Node(int val, Node* next  nullptr) : data(val), next(next) {}};// Recursive function to reverse the linked listNode* reverseRecursive(Node* head) {    // Base case: if the list is empty or only one node, return head    if (!head || !head-next) {        return head;    }    // Recursively reverse the remaining list    Node* newHead  reverseRecursive(head-next);    // Change the next nodes next pointer to point back to current node    head-next-next  head;    // Set the current nodes next pointer to nullptr    head-next  nullptr;    // Return the new head of the reversed list    return newHead;}// Helper function to print the linked listvoid printList(Node* head) {    while (head ! nullptr) {        cout  head-data  (head-next ?   : );        head  head-next;    }    cout  endl;}// Main function to demonstrate the recursive reversalint main() {    // Create a linked list: 1 - 2 - 3 - 4 - 5    Node* head  new Node(1);    head-next  new Node(2);    head-next-next  new Node(3);    head-next-next-next  new Node(4);    head-next-next-next-next  new Node(5);    cout  Original List: ;    printList(head);    // Reverse the linked list using recursion    head  reverseRecursive(head);    cout  Reversed List: ;    printList(head);    return 0;}

Explanation of the Code

Let's break down the code to understand how it works:

1. Base Case

If the list is empty !head or has only one node !head-next, the function simply returns the head as reversing a single node or empty list doesn't change anything.

2. Recursive Call

The function calls itself with the next node reverseRecursive(head-next) eventually reaching the last node.

3. Reverse the Links

The following steps reverse the links:

head-next-next head makes the next node point back to the current node.

head-next nullptr sets the current node's next pointer to nullptr, marking it as the end of the reversed list.

4. Return New Head

Finally, the last node newHead is returned up the recursive call stack.

Output

The output will be:

Original List: 1 2 3 4 5  Reversed List: 5 4 3 2 1

This code successfully reverses the linked list using recursion.

Keywords: link list, recursion, C code example, algorithm, data structure