Past exam question: 2066 Bhadra (Regular / Back), Q4
Open in the Padhaiko appQuestion
Write an algorithm to move one node to another place after a node in singly linear linked list.
Solution
Moving Node X to Appear Immediately After Node Y (X != Y): Let srcVal be the key of the node X to move, and dstVal be the key of the target node Y after which X should be placed:
- Locate
Xalong with its predecessorprevX(ifX == head,prevX = NULL). - Locate target node
Y. - If either
XorYis missing, orX == Y, orY->next == X(already right afterY), return without change. - Detach
Xfrom its old position:- If
prevX == NULL(Xwashead), sethead = X->next. - Else set
prevX->next = X->next.
- If
- Insert
XafterY:- Set
X->next = Y->next. - Set
Y->next = X.
- Set
Algorithm MOVE_AFTER(head, srcVal, dstVal):
Algorithm MOVE_AFTER(head, srcVal, dstVal):
1. If head == NULL or srcVal == dstVal: Return head
2. prevX = NULL, X = head
While X != NULL and X->data != srcVal:
prevX = X; X = X->next
3. Y = head
While Y != NULL and Y->data != dstVal:
Y = Y->next
4. If X == NULL or Y == NULL or Y->next == X:
Return head
5. If prevX == NULL:
head = X->next
Else:
prevX->next = X->next
6. X->next = Y->next
7. Y->next = X
8. Return headAnswer:
MOVE_AFTER locates node X (with predecessor prevX) and target node Y, unlinks X from prevX (or advances head if X == head), and splices X after Y via X->next = Y->next; Y->next = X in time and extra space.