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,

Linked List
Linked List

Reversed Linked List,

Reversed 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]

2 thoughts on “Reverse a Singly Linked List in a Single Iteration”

  1. I just have one remark. Using recursion could cause stack overflow. Available stack size could be significanly smaller than the length of heap allocated array.

  2. @Zbigniew: Could be the case if the list is really really long. But in most cases it should be fine though. But its a good thought since we can implement the same in an iterative way. A loop over the same code traversing the list should do it. 🙂

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top