Question

Write a routine to interchange the mth and nth elements of a singly-linked list. You may assume that the ranks m and n are passed in as parameters. Allow for all the ways that m and n can occur. You must rearrange the pointers, not simply swap the contents. Please use psuedocode

Answer 1

The routine to swap the two nodes ranked m and n in the form of psuedocode is provided below, please comment if any doubts:

//The routine to swap m th and nth ranked elements
void swapmAndn(int m, int n)
{
   //Set the linked list head node
   Linked_Node **node_head

   //To find the m ranked node
   //set previous node  
   Linked_Node *node_prev = NULL;
  
   //set node to store m ranked node as head node
   Linked_Node *node_current_m = *node_head;
  
   //set the rank as rm=1
   rm =1

   //traverse to find the m ranked node
   while (node_current_m && rm<m)
   {    
       node_prev = node_current_m;
       node_current_m = node_current_m->next;
       rm++;
   }
  
   //To find the n ranked node
   //set previous node  
   Linked_Node *node_prev_n = NULL;
  
   //set node to store n ranked node as head node
   Linked_Node *node_current_n = *node_head;
  
   //set the rank as rn=1
   rn =1

   //traverse to find the n ranked node
   while (node_current_n && rn<n)
   {    
       node_prev_n= node_current_n;
       node_current_n = node_current_n->next;
       rn++;
   }
  
   //if m is not first ranked node
   if (node_prev != NULL)
       //set node_current_n as previous node
       node_prev->next = node_current_n;
  
   //otherwise Set the node_current_n
   else
       *node_head = node_current_n;
  
   // If n is not first ranked node
   if (node_prev_n!= NULL)
       node_prev_n->next = node_current_m;
   else
       *node_head = node_current_m;
  
   //now swap the next pointers also
   //to make the swap process complete  
   Linked_Node *temp = node_current_n->next;
   node_current_n->next = node_current_m->next;
   node_current_m->next = temp;
}