Data Structures - Circular Singly Linked List Other Related Topics

Circular Singly Linked List - Swap node values



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(int node1, int node2) {
  
  //1. count the number of nodes in the list
  Node* temp = head;
  int N = 0;
  if(temp != NULL) {
    N++;
    temp = temp->next;
  }
  while(temp != head) {
    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
  Node* pos1 = head;
  Node* pos2 = head;
  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;
} 
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;   
}
def swapNodeValues(self, node1, node2):
  
  #1. count the number of nodes in the list
  temp = self.head
  N = 0
  if (temp != None):
    N += 1
    temp = temp.next
  while (temp != self.head):
    N += 1
    temp = temp.next

  #2. check if the swap positions are valid entries
  if(node1 < 1 or node1 > N or node2 < 1 or node2 > N):
    return

  #3. traverse to the nodes where values to be swapped
  pos1 = self.head
  pos2 = self.head
  for i in range(1, node1):
    pos1 = pos1.next;
  for i in range(1, node2):
    pos2 = pos2.next;

  #4. swap the values of two nodes
  val = pos1.data
  pos1.data = pos2.data
  pos2.data = val 
void swapNodeValues(int node1, int node2) {
  
  //1. count the number of nodes in the list
  Node temp = new Node();
  temp = this.head;
  int N = 0;
  if (temp != null) {
    N++;
    temp = temp.next;
  }
  while(temp != this.head) {
    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
  Node pos1 = this.head;
  Node pos2 = this.head;
  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;
}   
public void swapNodeValues(int node1, int node2) {
  
  //1. count the number of nodes in the list
  Node temp = new Node();
  temp = this.head;
  int N = 0;
  if (temp != null) {
    N++;
    temp = temp.next;
  }
  while(temp != this.head) {
    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
  Node pos1 = this.head;
  Node pos2 = this.head;
  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; 
}   
public function swapNodeValues($node1, $node2) {
  
  //1. count the number of nodes in the list
  $temp = new Node();
  $temp = $this->head;
  $N = 0;
  if ($temp != null) {
    $N++;
    $temp = $temp->next;
  }
  while($temp != $this->head) {
    $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
  $pos1 = $this->head;
  $pos2 = $this->head;
  for($i = 1; $i < $node1; $i++) {
    $pos1 = $pos1->next;
  }
  for($i = 1; $i < $node2; $i++) {
    $pos2 = $pos2->next;
  }

  //4. swap the values of two nodes
  $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 <iostream>
using namespace std;

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

class LinkedList {
  private:
    Node* head;
  public:
    LinkedList(){
      head = NULL;
    }
 
    //Add new element at the end of the list
    void push_back(int newElement) {
      Node* newNode = new Node();
      newNode->data = newElement;
      newNode->next = NULL; 
      if(head == NULL) {
        head = newNode;
        newNode->next = head;
      } else {
        Node* temp = head;
        while(temp->next != head)
          temp = temp->next;
        temp->next = newNode;
        newNode->next = head;
      }    
    }

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

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

      Node* pos1 = head;
      Node* pos2 = head;
      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() {
      Node* temp = head;
      if(temp != NULL) {
        cout<<"The list contains: ";
        while(true) {
          cout<<temp->data<<" ";
          temp = temp->next;
          if(temp == head) 
            break;
        }
        cout<<endl;
      } else {
        cout<<"The list is empty.\n";
      }
    }     
};

// test the code 
int main() {
  LinkedList MyList;

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

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

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

  //Display the content of the list.
  MyList.PrintList();
  
  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 
#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 
# node structure
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

#class Linked List
class LinkedList:
  def __init__(self):
    self.head = None

  #Add new element at the end of the list
  def push_back(self, newElement):
    newNode = Node(newElement)
    if(self.head == None):
      self.head = newNode
      newNode.next = self.head
      return
    else:
      temp = self.head
      while(temp.next != self.head):
        temp = temp.next
      temp.next = newNode
      newNode.next = self.head

  #swap node values
  def swapNodeValues(self, node1, node2):
    
    temp = self.head
    N = 0
    if (temp != None):
      N += 1
      temp = temp.next
    while (temp != self.head):
      N += 1
      temp = temp.next

    if(node1 < 1 or node1 > N or node2 < 1 or node2 > N):
      return

    pos1 = self.head
    pos2 = self.head
    for i in range(1, node1):
      pos1 = pos1.next;
    for i in range(1, node2):
      pos2 = pos2.next;

    val = pos1.data
    pos1.data = pos2.data
    pos2.data = val  

  #display the content of the list
  def PrintList(self):
    temp = self.head
    if(temp != None):
      print("The list contains:", end=" ")
      while (True):
        print(temp.data, end=" ")
        temp = temp.next
        if(temp == self.head):
          break
      print()
    else:
      print("The list is empty.")

# test the code                  
MyList = LinkedList()

#Add five elements in the list.
MyList.push_back(10)
MyList.push_back(20)
MyList.push_back(30)
MyList.push_back(40)
MyList.push_back(50)

#Display the content of the list.
MyList.PrintList()

#swap values of node=1 and node=4
MyList.swapNodeValues(1, 4)

#Display the content of the list.
MyList.PrintList()

The above code will give the following output:

The list contains: 10 20 30 40 50 
The list contains: 40 20 30 10 50 
//node structure
class Node {
    int data;
    Node next;
};

class LinkedList {
  Node head;

  LinkedList(){
    head = null;
  }

  //Add new element at the end of the list
  void push_back(int newElement) {
    Node newNode = new Node();
    newNode.data = newElement;
    newNode.next = null; 
    if(head == null) {
      head = newNode;
      newNode.next = head;
    } else {
      Node temp = new Node();
      temp = head;
      while(temp.next != head)
        temp = temp.next;
      temp.next = newNode;
      newNode.next = head;
    }    
  }

  //swap node values
  void swapNodeValues(int node1, int node2) {
    
    Node temp = new Node();
    temp = this.head;
    int N = 0;
    if (temp != null) {
      N++;
      temp = temp.next;
    }
    while(temp != this.head) {
      N++;
      temp = temp.next;
    } 

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

    Node pos1 = this.head;
    Node pos2 = this.head;
    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() {
    Node temp = new Node();
    temp = this.head;
    if(temp != null) {
      System.out.print("The list contains: ");
      while(true) {
        System.out.print(temp.data + " ");
        temp = temp.next;
        if(temp == this.head)
          break;
      }
      System.out.println();
    } else {
      System.out.println("The list is empty.");
    }
  }     
};

// test the code 
public class Implementation {
  public static void main(String[] args) {
    LinkedList MyList = new LinkedList();

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

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

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

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

The above code will give the following output:

The list contains: 10 20 30 40 50 
The list contains: 40 20 30 10 50 
using System;

//node structure
class Node {
  public int data;
  public Node next;
};

class LinkedList {
  Node head;

  public LinkedList(){
    head = null;
  }
  
  //Add new element at the end of the list
  public void push_back(int newElement) {
    Node newNode = new Node();
    newNode.data = newElement;
    newNode.next = null; 
    if(head == null) {
      head = newNode;
      newNode.next = head;
    } else {
      Node temp = new Node();
      temp = head;
      while(temp.next != head)
        temp = temp.next;
      temp.next = newNode;
      newNode.next = head;
    }    
  }

  //swap node values
  public void swapNodeValues(int node1, int node2) {
    
    Node temp = new Node();
    temp = this.head;
    int N = 0;
    if (temp != null) {
      N++;
      temp = temp.next;
    }
    while(temp != this.head) {
      N++;
      temp = temp.next;
    } 

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

    Node pos1 = this.head;
    Node pos2 = this.head;
    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
  public void PrintList() {
    Node temp = new Node();
    temp = this.head;
    if(temp != null) {
      Console.Write("The list contains: ");
      while(true) {
        Console.Write(temp.data + " ");
        temp = temp.next;
        if(temp == this.head)
          break;        
      }
      Console.WriteLine();
    } else {
      Console.WriteLine("The list is empty.");
    }
  }      
};

// test the code
class Implementation {  
  static void Main(string[] args) {
    LinkedList MyList = new LinkedList();

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

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

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

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

The above code will give the following output:

The list contains: 10 20 30 40 50 
The list contains: 40 20 30 10 50 
<?php
//node structure
class Node {
  public $data;
  public $next;
}

class LinkedList {
  public $head;

  public function __construct(){
    $this->head = null;
  }
  
  //Add new element at the end of the list
  public function push_back($newElement) {
    $newNode = new Node();
    $newNode->data = $newElement;
    $newNode->next = null; 
    if($this->head == null) {
      $this->head = $newNode;
      $newNode->next = $this->head;
    } else {
      $temp = new Node();
      $temp = $this->head;
      while($temp->next !== $this->head) {
        $temp = $temp->next;
      }
      $temp->next = $newNode;
      $newNode->next = $this->head;
    }    
  }

  //swap node values
  public function swapNodeValues($node1, $node2) {
    
    $temp = new Node();
    $temp = $this->head;
    $N = 0;
    if ($temp != null) {
      $N++;
      $temp = $temp->next;
    }
    while($temp != $this->head) {
      $N++;
      $temp = $temp->next;
    } 

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

    $pos1 = $this->head;
    $pos2 = $this->head;
    for($i = 1; $i < $node1; $i++) {
      $pos1 = $pos1->next;
    }
    for($i = 1; $i < $node2; $i++) {
      $pos2 = $pos2->next;
    }

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

  //display the content of the list
  public function PrintList() {
    $temp = new Node();
    $temp = $this->head;
    if($temp != null) {
      echo "The list contains: ";
      while(true) {
        echo $temp->data." ";
        $temp = $temp->next;
        if($temp == $this->head)
          break;        
      }
      echo "\n";
    } else {
      echo "The list is empty.\n";
    }
  }    
};

// test the code  
$MyList = new LinkedList();

//Add five elements in the list.
$MyList->push_back(10);
$MyList->push_back(20);
$MyList->push_back(30);
$MyList->push_back(40);
$MyList->push_back(50);

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

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

//Display the content of the list.
$MyList->PrintList();
?>

The above code will give the following output:

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