Tuesday, January 7, 2014

Reversing circular singley link list

In last post we have see how to reverse the single link list. We had used the iterative method to reverse the list.
Consider that you have a circular list as shown below.
Now you have to reverse the list and break the circle.
Now you can use same approach of finding out the loop in the list as discussed in the previous post. Then reverse the list recursively. 

One thing to note here is that once you find out that there is loop in the list then find out the last node of the list and then you will have to break the loop.

void ReverseCircularSinglyList(Node *pHead, Node *pHeadNext, Node * pFar, Node * pOrgHead, bool & bFoundLoop, Node * & pNewHead)
{
    if (pHead)
    {
        if (pHead->pNext == NULL)
            pNewHead = pHead;

        if (!bFoundLoop)
        {
            Node * pTemp = pHead ->pNext;
            if (pFar)
                pFar = pFar->pNext;
            else
                bFoundLoop = true;

            if (pFar)
                pFar = pFar -> pNext;
            else
                bFoundLoop = true;

            if (pFar == pTemp)
            {
                bFoundLoop = true;
                //found the circle
                //Now search the starting point of the circle.
                pTemp = NULL;
                while (pOrgHead != pFar)
                {
                    pTemp = pFar;
                    pOrgHead = pOrgHead->pNext;
                    pFar = pFar -> pNext;
                }

                pTemp->pNext = NULL;
            }
        }
        ReverseCircularSinglyList(pHead->pNext, pHead, pFar, pOrgHead, bFoundLoop, pNewHead);
        pHead->pNext = pHeadNext;
    }
}

Node * ReverseCircularSLL(Node * pHead)
{
    Node * pNewHead = NULL;
    bool bFoundLoop = false;
    ReverseCircularSinglyList(pHead, NULL, pHead, pHead, bFoundLoop, pNewHead);
    return pNewHead;
}

No comments:

Post a Comment