Program to reverse link list using recursion C++

Here is the code : Debug, Run and Learn


#include <iostream>
#include <conio.h>

using namespace std;
struct node
{
  int data;
  node *next;

  node(int d, node *n = NULL) : data(d), next(n)
  {
  }
};

class link_list
{
public:
  node *head;

  link_list(int val)
  {
    head = new node(val);
  }

  link_list() : head(NULL) {}

  void push(int val)
  {
    if (head == NULL)
    {
      head = new node(val);
    }
    else
    {
      node *current = head;

      for (; current->next != NULL; current = current->next);

      current->next = new node(val);
    }
  }

  void reverse_recursive(node **start)
  {
    if (*start == NULL || (*start)->next == NULL) return;

    node *first = *start;
    node *rest = first->next;

    reverse_recursive(&rest);

    first->next->next = first;
    first->next = NULL;

    *start = rest;
  }

  void reverse(void)
  {
    node *current = head;
    node *prev = NULL;
    node *next = NULL;

    while (current != NULL)
    {
      next = current->next;
      current->next = prev;

      prev = current;
      current = next;
    }

    head = prev;
  }

    void print(void)
    {
      cout << endl << "Link list is :" << endl;
      

      for (node *current = head; current != NULL; current = current->next)
      {
        cout << current->data << "-->";
      }

      cout << "NULL";
    }
};
void main()
{
  link_list Llist(1);

  for (int index = 2; index <= 10; ++index) Llist.push(index);

  cout << endl << "Before reverse" << endl;
  Llist.print();
  
  Llist.reverse_recursive(&Llist.head);

  cout << endl << endl << "After recursive reverse" << endl;
  Llist.print();


  Llist.reverse();
  cout << endl << endl << "Again simple reverse" << endl;
  Llist.print();
  
  _getch();
}


Output

Before reverse Link list is : 1-->2-->3-->4-->5-->6-->7-->8-->9-->10-->NULL After recursive reverse Link list is : 10-->9-->8-->7-->6-->5-->4-->3-->2-->1-->NULL Again simple reverse Link list is : 1-->2-->3-->4-->5-->6-->7-->8-->9-->10-->NULL

Thanks

Comments

Popular Posts