Question: Write a C++ function that takes a singularly-linked list and recursively reverses it. It must have linear, O(n), run time - that is you are only allowed to make 1 pass through the list. No changes to the list data can be made and no additional data structures can be used.

This is very similar to the non-recursive linked list reverse problem.

Solution: My approach to this problem is to use the recursion to drill into the list and to do the pointer swapping on the way back up the recursive call stack. In lines 18-28 below we call the function recursively until we have reached the end of the linked list which is determined by the NULL node pointer checks. Lines 30-32 do not get called until we have gotten to the end of the linked list and we are on our way back up the call stack. These lines merely set the "next" pointer for the current element to point to the previous element, and remove the "next" pointer on the current pointer. The head of the list is then updated.

Here's my C++ code to do this:

   1:  #include <stdio.h>
   2:  #include <stdafx.h>
   3:  #include <malloc.h>
   4:   
   5:  struct node{
   6:      int data;
   7:      node* next;
   8:  };
   9:   
  10:  void push(node** head, int data){
  11:      node* newNode = new node;    // struct keyword not necessary in C++
  12:      newNode->data = data;
  13:      newNode->next = *head;
  14:      *head = newNode;
  15:  }
  16:   
  17:  void recursiveReverse(node** start){
  18:      node* current = *start;
  19:      
  20:      if (current == NULL)
  21:          return;
  22:   
  23:      node* rest = current->next;
  24:      
  25:      if (rest == NULL)
  26:          return;
  27:   
  28:      recursiveReverse(&rest);
  29:   
  30:      current->next->next = current;
  31:      current->next=NULL;
  32:      *start=rest;
  33:  }
  34:   
  35:  int main(){
  36:      
  37:      node* head= NULL;    
  38:          
  39:      for(int i=7; i>=1;i--){
  40:          push(&head, i);
  41:      }
  42:      
  43:      node* current = head;
  44:      while(current != NULL){
  45:          printf("%d ",current->data);
  46:          current = current->next;
  47:      }
  48:   
  49:      recursiveReverse(&head);
  50:      printf("\n");
  51:   
  52:      current = head;
  53:      while(current != NULL){
  54:          printf("%d ",current->data);
  55:          current = current->next;
  56:      }
  57:  }
Bookmark and Share