Swap nodes in a linked list without swapping data - GeeksforGeeks

Swap nodes in a linked list without swapping data - GeeksforGeeks
Given a linked list and two keys in it, swap nodes for two given keys. Nodes should be swapped by changing links. Swapping data of nodes may be expensive in many situations when data contains many fields.
1) x and y may or may not be adjacent.
2) Either x or y may be a head node.
3) Either x or y may be last node.
4) x and/or y may not be present in linked list.

void swapNodes(struct node **head_ref, int x, int y)

{

   // Nothing to do if x and y are same

   if (x == y) return;

 

   // Search for x (keep track of prevX and CurrX

   struct node *prevX = NULL, *currX = *head_ref;

   while (currX && currX->data != x)

   {

       prevX = currX;

       currX = currX->next;

   }

 

   // Search for y (keep track of prevY and CurrY

   struct node *prevY = NULL, *currY = *head_ref;

   while (currY && currY->data != y)

   {

       prevY = currY;

       currY = currY->next;

   }

 

   // If either x or y is not present, nothing to do

   if (currX == NULL || currY == NULL)

       return;

 

   // If x is not head of linked list

   if (prevX != NULL)

       prevX->next = currY;

   else // Else make y as new head

       *head_ref = currY; 

 

   // If y is not head of linked list

   if (prevY != NULL)

       prevY->next = currX;

   else  // Else make x as new head

       *head_ref = currX;

 

   // Swap next pointers

   struct node *temp = currY->next;

   currY->next = currX->next;

   currX->next  = temp;

}

Read full article from Swap nodes in a linked list without swapping data - GeeksforGeeks