Reverse a Singly Linked List in a Single Iteration

Suppose we have a linked list and we want to reverse it in Single iteration and O(n) complexity.

Original Linked List,

Reversed Linked List,

Our Node structure is,

struct node
{
    int value;
    node * nextPtr;    
    node(int val)
    {
        value = val;
        nextPtr = NULL;    
    }
};

Now we will create a function to reverse it.

This function will accept 2 parameters i.e.
1.) Node to reverse
2.) Pevious node pointer.

We will call this function with default value for last parameter i.e.

    node * ptr = createListFromArray(arr, sizeof(arr)/sizeof(int));
    ptr = reverseList(ptr);

Inside this reverseList function,

If given pointer ptr is NULL it means you have reached the end of linked list, so just return the previous
node because that will be the last Node.
Store the next pointer of passed ptr i.e. ptr->nextPtr in a variable and make ptr->nextPtr to passed previous node.

Now again call the reverseList with next node pointer stored earlier and current node as the previous node.
In the end return last node of original list because now it will be root node of reversed linked list.

[showads ad=inside_post]

Here is the reverse function code,

node * reverseList(node * ptr, node * prevNode = NULL)
{
    if(!ptr)
        return prevNode;
    node * pNext = ptr->nextPtr;
    ptr->nextPtr = prevNode;
    return reverseList(pNext, ptr);
}

Full Code example is as follows,

[code language=”cpp”]
#include <iostream>
/*
 * Node will contain and int variable as value
 * and a node pointer to next Node.
 **/
struct node
{
    int value;
    node * nextPtr;    
    node(int val)
    {
        value = val;
        nextPtr = NULL;    
    }
};

/*
*  If given pointer ptr is NULL it means you have reached
*  the end of linked list, so just return the previous
*  node because that will be the last Node.
*  
*  Store the next pointer of passed ptr i.e. ptr->nextPtr
*  in a variable and make ptr->nextPtr to passed previous node.
*  
*  Now again call the reverseList with next node pointer stored
*  earlier and current node as the previous node.
*  
*  In the end return last node of original list because now it
*  will be root node of reversed linked list.
**/
node * reverseList(node * ptr, node * prevNode = NULL)
{
    
    if(!ptr)
        return prevNode;
    node * pNext = ptr->nextPtr;
    ptr->nextPtr = prevNode;
    return reverseList(pNext, ptr);
}

/*
 * Iterate the passed array one by one and create a node
 * for each element and append it in last node’s next pointer.
 * Also keep a track of last node created while iteration to
 * update its next pointer in next iteration.
 * Also store the first node created,that we will returned as
 * root node in end.
**/
node * createListFromArray(int * ptr, int arraySize)
{
    node * nodePtr = NULL;
    node * rootNodePtr = NULL;
    node * lastNodePtr = NULL;
    for(int i = 0 ; i < arraySize; i++)
    {
        if(!nodePtr)
        {
            nodePtr = new node(*(ptr+i));
            if(!rootNodePtr)
                rootNodePtr = nodePtr;    
            if(lastNodePtr)    
                lastNodePtr->nextPtr = nodePtr;
        }
        lastNodePtr = nodePtr;
        nodePtr = nodePtr->nextPtr;
    }
    return rootNodePtr;
}
/*
 * Store the next pointer of passed node as temp variable.
 * Delete the current pointer and pass the earlier stored next pointer
 * to destroyList funtion.
 *
 * If ptr is null it means its the end of linked list, so just return
 * because complete linked list is deleted.
 **/
void destroyList(node * ptr)
{
    if(ptr)
    {
        node * pNext = ptr->nextPtr;
        delete ptr;
        destroyList(pNext);
    }
}
/*
 * Iterate through all nodes and display content
 * of each node untill end of linked list is reached.
 **/
void displayLinkedList(node *ptr)
{
    while(ptr != NULL)
    {
        std::cout<<ptr->value<<” “;
        ptr = ptr->nextPtr;
    }
    std::cout<<std::endl;
}
/*
 * Testing functions.
 **/
int main()
{
    int arr[] = {1,2,3,4, 89,1,1,1,0};
    node * ptr = createListFromArray(arr, sizeof(arr)/sizeof(int));
    displayLinkedList(ptr);
    ptr = reverseList(ptr);
    displayLinkedList(ptr);
    destroyList(ptr);
    return 0;
}

[/code]