Question: Write a C++ function that takes a singularly-linked list and 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 similar to the recursive reverse problem.

Solution: This is an exercise in pointer manipulation and understanding the difference between pass by value and pass by reference. All we need to do is to traverse the list keeping a reference/pointer to the last node visited and for the current node tweak the "next" pointer to point to the last node. Of course, before we overwrite the "next" pointer we need to take a copy of it first, otherwise we wouldn't be able to continue the list traversal. The hidden danger in this problem is making sure the head pointer is accurate at the end of the list traversal.

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 reverse(node** head){
  18:      node* current = *head;
  19:      node* last = NULL;
  20:      node* oldNext = current;
  21:   
  22:      while (current != NULL){
  23:          oldNext = current->next;
  24:          current->next = last;
  25:          last = current;
  26:          current = oldNext;
  27:      }
  28:      *head=last;
  29:  }
  30:   
  31:  int main(){
  32:      
  33:      node* head= NULL;    
  34:          
  35:      for(int i=7; i>=1;i--){
  36:          push(&head, i);
  37:      }
  38:      
  39:      node* current = head;
  40:      while(current != NULL)
  41:      {
  42:          printf("%d ",current->data);
  43:          current = current->next;
  44:      }
  45:   
  46:      reverse(&head);
  47:      printf("\n");
  48:   
  49:      current = head;
  50:      while(current != NULL)
  51:      {
  52:          printf("%d ",current->data);
  53:          current = current->next;
  54:      }
  55:  }

In the code above we use 3 node pointers (in lines 18-20) to keep track of the current node and the one before and after it. Along these same lines there is an alternative approach to the reverse problem that employs 3 iterators, called back, middle, front which effectively does the same thing as the algorithm above. For completeness, here is the 3-iterators approach:

   1:  // the three-pointer approach
   2:  void reverse2(node** head){
   3:      if (*head != NULL){
   4:          node* middle=*head;
   5:          node* front =middle->next;
   6:          node* back=NULL;
   7:          
   8:          while(true){
   9:              middle->next = back;    // reverse the middle node
  10:              
  11:              // move all pointers forward
  12:              if (front == NULL)
  13:                  break;
  14:   
  15:              back = middle;
  16:              middle = front; 
  17:              front = front->next;
  18:          }
  19:          *head = middle;
  20:      }
  21:  }
Bookmark and Share