C# program to reverse a LinkedList using recursion

Here's a C# program that reverses a LinkedList using recursion:

using System;

class Node
{
    public int Data;
    public Node Next;

    public Node(int data)
    {
        Data = data;
        Next = null;
    }
}

class LinkedList
{
    private Node Head;

    public LinkedList()
    {
        Head = null;
    }

    public void AddNode(int data)
    {
        Node newNode = new Node(data);

        if (Head == null)
        {
            Head = newNode;
        }
        else
        {
            Node current = Head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = newNode;
        }
    }

    public void Display()
    {
        Node current = Head;
        while (current != null)
        {
            Console.Write(current.Data + " ");
            current = current.Next;
        }
        Console.WriteLine();
    }

    public void Reverse()
    {
        Head = ReverseRecursively(Head);
    }

    private Node ReverseRecursively(Node current)
    {
        // Base case: if the current node is null or the last node in the list
        if (current == null || current.Next == null)
        {
            return current;
        }

        // Recursive case: reverse the rest of the list starting from the next node
        Node nextNode = current.Next;
        current.Next = null;
        Node reversedList = ReverseRecursively(nextNode);
        nextNode.Next = current;

        return reversedList;
    }
}

class Program
{
    static void Main()
    {
        LinkedList linkedList = new LinkedList();
        linkedList.AddNode(1);
        linkedList.AddNode(2);
        linkedList.AddNode(3);
        linkedList.AddNode(4);
        linkedList.AddNode(5);

        Console.WriteLine("Original LinkedList:");
        linkedList.Display();

        linkedList.Reverse();

        Console.WriteLine("Reversed LinkedList:");
        linkedList.Display();
    }
}

In this program, we have a Node class that represents a node in the LinkedList. Each node contains an integer Data and a reference to the next node Next.

The LinkedList class represents the LinkedList and contains methods to add nodes, display the LinkedList, and reverse the LinkedList.

To reverse the LinkedList using recursion, we have the Reverse method in the LinkedList class. This method calls the private helper method ReverseRecursively with the Head of the LinkedList.

The ReverseRecursively method is a recursive method that takes a Node as input and returns the reversed LinkedList starting from that node. It uses a divide-and-conquer approach.

In the base case, if the current node is null or the last node in the list (current.Next is null), we return the current node as it will be the new head of the reversed LinkedList.

In the recursive case, we reverse the rest of the list starting from the next node (obtained by current.Next). We store the next node in a temporary variable. Then, we set the Next of the current node to null to detach it from the rest of the list. We recursively call ReverseRecursively with the next node to get the reversed list starting from that node. Finally, we set the Next of the next node to the current node to link them in the reversed order.

In the Main method, we create a LinkedList, add nodes, display the original LinkedList, reverse it using the Reverse method, and display the reversed LinkedList.

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