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.
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