Reverse a Linked List

This is a short post but this topic deserved it’s own post. As I had mentioned before, the order in which you manipulate the pointers is extremely critical. Reversing a linked list can become quite complicated if you do not pay close attention to the order.

Consider the following linked list made up of 4 nodes. The head pointer points to the start of the list.  

To reverse this list, we need 3 additional pointers.  We need a currentNode pointer to traverse through the list, a nextNode pointer to save the next node in the list,  and finally, a prevNode pointer to keep track of the last node in the new list as we keep on reversing the input list. So, in essence, here is the pseudo algorithm to reverse the list:

• Initialize currentNode pointer to the start of the list and prevNode to NULL (as the new list is currently pointing to NULL).
• While currentNode is not NULL
• Save the next node in nextNode
• Set the currentNode to point to the prevNode. 
• Move the prevNode to the currentNode.
• Move the currentNode pointer to the nextNode.

Look at the following representations to better understand the concept outlined.

Step 1: setup

 

Step 2: Set the currentNode to point to the prevNode

Step 3: Move the pointers

Add the process continues till the list has been reversed. As the last step, you need to reset the head pointer to point to the prevNode as that is now the current head of the reversed list. Once you have understood the logic, the code part is actually quite simple as shown in the function below.

void Reverse()
{
    // Initialize currentNode pointer to the start of the list 
    // and prevNode to NULL 
    // (as the new list is currently pointing to NULL).
    Node *currentNode = head;
    Node *prevNode = NULL;
    Node *nextNode = NULL;

    while (currentNode != NULL)
    {
        // Save the next node in nextNode 
        nextNode = currentNode->next;
        // Set the currentNode to point to the prevNode.  
        currentNode->next = prevNode;
        // Move the prevNode to the currentNode.
        prevNode = currentNode;
        // Move the currentNode pointer to the nextNode.
        currentNode = nextNode;
    }

    // reset the head pointer to point to the prevNode 
    // as that is now the current head of the reversed list
    head = prevNode;
}