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.

Answer 1

Answer:

//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;

}

Explanation: