PadhaikoAll subjects

Past exam question: 2066 Bhadra (Regular / Back), Q4

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Linked List

Question

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:

  1. Locate X along with its predecessor prevX (if X == head, prevX = NULL).
  2. Locate target node Y.
  3. If either X or Y is missing, or X == Y, or Y->next == X (already right after Y), return without change.
  4. Detach X from its old position:
    • If prevX == NULL (X was head), set head = X->next.
    • Else set prevX->next = X->next.
  5. Insert X after Y:
    • Set X->next = Y->next.
    • Set Y->next = X.

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 head
Answer:

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.

All past exam questions for Data Structure and Algorithms