C Data Structures - Circular Singly Linked List Other Related Topics

C - Swap node values of a Circular Singly Linked List



There are many instances where it is required to swap value of two nodes while working with a list. This can be achieved by traversing to the interested nodes and swap their values if the nodes are valid. For example - if the given list is 10->20->30->40->50. After swapping values of first and fourth nodes, the list will become 40->20->30->10->50.

The function swapNodeValues is created for this purpose which is a 4-step process.

void swapNodeValues(struct Node* head_ref, int node1, int node2) {
  
  //1. count the number of nodes in the list
  struct Node* temp = head_ref;
  int N = 0;
  if(temp != NULL) {
    N++;
    temp = temp->next;
  }
  while (temp != head_ref) {
    N++;
    temp = temp->next;    
  }

  //2. check if the swap positions are valid entries
  if(node1 < 1 || node1 > N || node2 < 1 || node2 > N)
    return;

  //3. traverse to the nodes where values to be swapped
  struct Node* pos1 = head_ref;
  struct Node* pos2 = head_ref;
  for(int i = 1; i < node1; i++) {
    pos1 = pos1->next;
  }
  for(int i = 1; i < node2; i++) {
    pos2 = pos2->next;
  }

  //4. swap the values of two nodes
  int val = pos1->data;
  pos1->data = pos2->data;
  pos2->data = val;   
}

The below is a complete program that uses above discussed concept to swap values of two given nodes of a circular singly linked list.

#include <stdio.h>
#include <stdlib.h>

//node structure
struct Node {
  int data;
  struct Node* next;
};

//Add new element at the end of the list
void push_back(struct Node** head_ref, int newElement) {  
  struct Node *newNode, *temp;
  newNode = (struct Node*)malloc(sizeof(struct Node)); 
  newNode->data = newElement;  
  newNode->next = NULL;
  if(*head_ref == NULL) {
    *head_ref = newNode;
     newNode->next = *head_ref;
  } else {
    temp = *head_ref;
    while(temp->next != *head_ref) {
      temp = temp->next;
    }    
    temp->next = newNode;
    newNode->next = *head_ref;
  }
}

//swap node values
void swapNodeValues(struct Node* head_ref, int node1, int node2) {
  
  struct Node* temp = head_ref;
  int N = 0;
  if(temp != NULL) {
    N++;
    temp = temp->next;
  }
  while (temp != head_ref) {
    N++;
    temp = temp->next;    
  }

  if(node1 < 1 || node1 > N || node2 < 1 || node2 > N)
    return;

  struct Node* pos1 = head_ref;
  struct Node* pos2 = head_ref;
  for(int i = 1; i < node1; i++) {
    pos1 = pos1->next;
  }
  for(int i = 1; i < node2; i++) {
    pos2 = pos2->next;
  }

  int val = pos1->data;
  pos1->data = pos2->data;
  pos2->data = val;   
}

//display the content of the list
void PrintList(struct Node* head_ref) {
  struct Node* temp = head_ref;
  if(head_ref != NULL) {
    printf("The list contains: ");
    while (1) {
      printf("%i ",temp->data);
      temp = temp->next;
      if(temp == head_ref)
        break;    
    }
    printf("\n");
  } else {
    printf("The list is empty.\n");
  }   
}

// test the code 
int main() {
  struct Node* MyList = NULL;

  //Add five elements in the list.
  push_back(&MyList, 10);
  push_back(&MyList, 20);
  push_back(&MyList, 30);
  push_back(&MyList, 40);
  push_back(&MyList, 50);

  //Display the content of the list.
  PrintList(MyList);

  //swap values of node=1 and node=4
  swapNodeValues(MyList, 1, 4);

  //Display the content of the list.
  PrintList(MyList);

  return 0; 
}

The above code will give the following output:

The list contains: 10 20 30 40 50 
The list contains: 40 20 30 10 50