Linked List: Reverse

Question: Given the head pointer to a singly linked list reverse the list.

Solution 1: Recursive Approach - We can recursively traverse the linked list till we arrive at the last but one node. We then set the next pointer of the last node to point to the current node. We keep reversing the links as we unwind the recursive calls.

Code:

// Takes a pointer to the head node of a singly linked list
// and returns the new head pointer for the reversed list
Node * Reverse(Node * head)
{
   Node *newHead = Recursive_Reverse(head);
   head->next = NULL;      // since the first node is the last node now
                           // we need to set it's next pointer to NULL
   return newHead;
}

Node * Recursive_Reverse(Node * node)
{
   Node *nextNode = node->next;
   if(nextNode == NULL)       // if the list has only one node
   {                          // we don't need to reverse it
       return node;
   }

   if(nextNode->next == NULL) // if nextNode is the last node we terminate the recursion
   {
       nextNode->next = node; // reverse the link
       return nextNode;       // return the ptr to the last node
                              // this will become the new head pointer
   }
   Node *head = Reverse(node->next); //recursively call Reverse
   nextNode->next = node;     // reverse the link
   return head;             
}

Solution 2: We can also reverse the singly linked list using an iterative approach. For some this approach can be easier to understand. Basically, we maintain 3 pointers (prevNode, currentNode, and nextNode). At each step we save the next of the currentNode in the nextNode ptr and reverse the link. After this, we advance the previous and current pointers.

Code:

//Takes a pointer to the head of a linked list
//Returns the pointer to the new head (old tail) node
Node * Iterative_Reverse(Node *head)
{
   Node *prevNode = NULL;      //pointer to the previous node
   Node *nextNode = NULL;      //pointer to the next node
   Node *currentNode = head;   //pointer to the current node
   while(currentNode)
   {
       nextNode = currentNode->next; //save the pointer to the next node
                                     //otherwise we will lose it as we
                                     // overwrite it in the next step
       currentNode->next = prevNode; //reverse the link
      
       prevNode = currentNode; //set the current node as the previous node
                               //for the next iteration
       currentNode = nextNode; //advance the current pointer
   }
   return prevNode;
}