Wednesday, January 22, 2014

Swaping kth node from start and kth node from end from the singly link list

In order to  swap the linked list nodes you will require the previous nodes of the nodes to be swapped so that you can maintain the list.
 
We already know how to find the kth node from the end of the singly link list. We will first search for the kth node from the start and its previous node. Then we will find out the kth node from the end and its previous node. 

Then swapping these nodes will be a easy task.


//Code returns the head of the modified list.
Node * SwapKthNodes(Node * pHead, int nKth)
{
    if (pHead)
    {
        Node * pKth = pHead;
        Node * pKthPrev = NULL;
        int i = 1;
        while (pKth && i < nKth)
        {
            i++;
            pKthPrev = pKth;
            pKth = pKth->pNext;
        }


        //Didn't find the kth element
        if (!pKth)
            return pHead;

        Node * temp = pKth;
        Node * pKthFromEnd = pHead;
        Node * pKthPrevFromEnd = NULL;

        //Searching the Kth node from end
        while (temp->pNext)
        {
            pKthPrevFromEnd = pKthFromEnd;
            pKthFromEnd = pKthFromEnd->pNext;
            temp = temp->pNext;
        }

        if (pKthFromEnd == pKth)
            return pHead;
        //kthpos == 1
        if (!pKthPrev)
        {
            pKthPrevFromEnd->pNext = pHead;
            Node * pTemp = pHead->pNext;
            pHead->pNext = pKthFromEnd->pNext;
            pKthFromEnd->pNext = pTemp;
            return pKthFromEnd;
        }

        //KthFrom end might be the first node
        if (!pKthPrevFromEnd)
        {
            Node * pTemp = pKthFromEnd->pNext;
            pKthFromEnd->pNext = pKth->pNext;
            pKth->pNext = pTemp;

            pKthPrev->pNext = pKthFromEnd;

            return pKth;
        }
        pKthPrevFromEnd->pNext = pKth;
        Node * pTemp = pKth->pNext;
        pKthPrev->pNext = pKthFromEnd;
        Node * pTemp2 = pKthFromEnd->pNext;
        pKthFromEnd->pNext = pTemp;
        pKth->pNext = pTemp2;

        return pHead;
    }

    return NULL;
}

No comments:

Post a Comment