C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML
Program to swap nodes in a singly linked list without swapping dataExplanationIn this program, we need to swap given two nodes in the singly linked list without swapping data. ![]() One of the approaches to accomplish this task is to swap the previous nodes of the given two nodes and then, swap the next nodes of two nodes. Algorithm
SolutionPython#Represent a node of the singly linked list class Node: def __init__(self,data): self.data = data; self.next = None; class SwapNodes: #Represent the head and tail of the singly linked list def __init__(self): self.head = None; self.tail = None; #addNode() will add a new node to the list def addNode(self, data): #Create a new node newNode = Node(data); #Checks if the list is empty if(self.head == None): #If list is empty, both head and tail will point to new node self.head = newNode; self.tail = newNode; else: #newNode will be added after tail such that tail's next will point to newNode self.tail.next = newNode; #newNode will become new tail of the list self.tail = newNode; #swap() will swap the given two nodes def swap(self, n1, n2): prevNode1 = None; prevNode2 = None; node1 = self.head; node2 = self.head; #Checks if list is empty if(self.head == None): return; #If n1 and n2 are equal, then list will remain the same if(n1 == n2): return; #Search for node1 while(node1 != None and node1.data != n1): prevNode1 = node1; node1 = node1.next; #Search for node2 while(node2 != None and node2.data != n2): prevNode2 = node2; node2 = node2.next; if(node1 != None and node2 != None): #If previous node to node1 is not None then, it will point to node2 if(prevNode1 != None): prevNode1.next = node2; else: self.head = node2; #If previous node to node2 is not None then, it will point to node1 if(prevNode2 != None): prevNode2.next = node1; else: self.head = node1; #Swaps the next nodes of node1 and node2 temp = node1.next; node1.next = node2.next; node2.next = temp; else: print("Swapping is not possible"); #display() will display all the nodes present in the list def display(self): #Node current will point to head current = self.head; if(self.head == None): print("List is empty"); return; while(current != None): #Prints each node by incrementing pointer print(current.data), current = current.next; sList = SwapNodes(); #Add nodes to the list sList.addNode(1); sList.addNode(2); sList.addNode(3); sList.addNode(4); sList.addNode(5); print("Original list: "); sList.display(); #Swaps the node 2 with node 5 sList.swap(2,5); print("List after swapping nodes: "); sList.display(); Output: Original list: 1 2 3 4 5 List after swapping nodes: 1 5 3 4 2 C#include <stdio.h> //Represent a node of the singly linked list struct node{ int data; struct node *next; }; //Represent the head and tail of the singly linked list struct node *head, *tail = NULL; //addNode() will add a new node to the list void addNode(int data) { //Create a new node struct node *newNode = (struct node*)malloc(sizeof(struct node)); newNode->data = data; newNode->next = NULL; //Checks if the list is empty if(head == NULL) { //If list is empty, both head and tail will point to new node head = newNode; tail = newNode; } else { //newNode will be added after tail such that tail's next will point to newNode tail->next = newNode; //newNode will become new tail of the list tail = newNode; } } //swap() will swap the given two nodes void swap(int n1, int n2){ struct node *prevNode1 = NULL, *prevNode2 = NULL, *node1 = head, *node2 = head, *temp = NULL; //Checks if list is empty if(head == NULL) { return; } //If n1 and n2 are equal, then list will remain the same if(n1 == n2) return; //Search for node1 while(node1 != NULL && node1->data != n1){ prevNode1 = node1; node1 = node1->next; } //Search for node2 while(node2 != NULL && node2->data != n2){ prevNode2 = node2; node2 = node2->next; } if(node1 != NULL && node2 != NULL) { //If previous node to node1 is not null then, it will point to node2 if(prevNode1 != NULL) prevNode1->next = node2; else head = node2; //If previous node to node2 is not null then, it will point to node1 if(prevNode2 != NULL) prevNode2->next = node1; else head = node1; //Swaps the next nodes of node1 and node2 temp = node1->next; node1->next = node2->next; node2->next = temp; } else{ printf("Swapping is not possible\n"); } } //display() will display all the nodes present in the list void display() { //Node current will point to head struct node *current = head; if(head == NULL) { printf("List is empty\n"); return; } while(current != NULL) { //Prints each node by incrementing pointer printf("%d ", current->data); current = current->next; } printf("\n"); } int main() { //Add nodes to the list addNode(1); addNode(2); addNode(3); addNode(4); addNode(5); printf("Original list: \n"); display(); //Swaps the node 2 with node 5 swap(2,5); printf("List after swapping nodes: \n"); display(); return 0; } Output: Original list: 1 2 3 4 5 List after swapping nodes: 1 5 3 4 2 JAVApublic class SwapNodes { //Represent a node of the singly linked list class Node{ int data; Node next; public Node(int data) { this.data = data; this.next = null; } } //Represent the head and tail of the singly linked list public Node head = null; public Node tail = null; //addNode() will add a new node to the list public void addNode(int data) { //Create a new node Node newNode = new Node(data); //Checks if the list is empty if(head == null) { //If list is empty, both head and tail will point to new node head = newNode; tail = newNode; } else { //newNode will be added after tail such that tail's next will point to newNode tail.next = newNode; //newNode will become new tail of the list tail = newNode; } } //swap() will swap the given two nodes public void swap(int n1, int n2){ Node prevNode1 = null, prevNode2 = null, node1 = head, node2 = head; //Checks if list is empty if(head == null) { return; } //If n1 and n2 are equal, then list will remain the same if(n1 == n2) return; //Search for node1 while(node1 != null && node1.data != n1){ prevNode1 = node1; node1 = node1.next; } //Search for node2 while(node2 != null && node2.data != n2){ prevNode2 = node2; node2 = node2.next; } if(node1 != null && node2 != null) { //If previous node to node1 is not null then, it will point to node2 if(prevNode1 != null) prevNode1.next = node2; else head = node2; //If previous node to node2 is not null then, it will point to node1 if(prevNode2 != null) prevNode2.next = node1; else head = node1; //Swaps the next nodes of node1 and node2 Node temp = node1.next; node1.next = node2.next; node2.next = temp; } else { System.out.println("Swapping is not possible"); } } //display() will display all the nodes present in the list public void display() { //Node current will point to head Node current = head; if(head == null) { System.out.println("List is empty"); return; } while(current != null) { //Prints each node by incrementing pointer System.out.print(current.data + " "); current = current.next; } System.out.println(); } public static void main(String[] args) { SwapNodes sList = new SwapNodes(); //Add nodes to the list sList.addNode(1); sList.addNode(2); sList.addNode(3); sList.addNode(4); sList.addNode(5); System.out.println("Original list: "); sList.display(); //Swaps the node 2 with node 5 sList.swap(2,5); System.out.println("List after swapping nodes: "); sList.display(); } } Output: Original list: 1 2 3 4 5 List after swapping nodes: 1 5 3 4 2 C#using System; public class CreateList { //Represent a node of the singly linked list public class Node<T>{ public T data; public Node<T> next; public Node(T value) { data = value; next = null; } } public class SwapNodes<T>{ //Represent the head and tail of the singly linked list public Node<T> head = null; public Node<T> tail = null; //addNode() will add a new node to the list public void addNode(T data) { //Create a new node Node<T> newNode = new Node<T>(data); //Checks if the list is empty if(head == null) { //If list is empty, both head and tail will point to new node head = newNode; tail = newNode; } else { //newNode will be added after tail such that tail's next will point to newNode tail.next = newNode; //newNode will become new tail of the list tail = newNode; } } //swap() will swap the given two nodes public void swap(int n1, int n2){ Node<T> prevNode1 = null, prevNode2 = null, node1 = head, node2 = head; //Checks if list is empty if(head == null) { return; } //If n1 and n2 are equal, then list will remain the same if(n1 == n2) return; //Search for node1 while(node1 != null && !(node1.data.Equals(n1))){ prevNode1 = node1; node1 = node1.next; } //Search for node2 while(node2 != null && !(node2.data.Equals(n2))){ prevNode2 = node2; node2 = node2.next; } if(node1 != null && node2 != null) { //If previous node to node1 is not null then, it will point to node2 if(prevNode1 != null) prevNode1.next = node2; else head = node2; //If previous node to node2 is not null then, it will point to node1 if(prevNode2 != null) prevNode2.next = node1; else head = node1; //Swaps the next nodes of node1 and node2 Node<T> temp = node1.next; node1.next = node2.next; node2.next = temp; } else { Console.WriteLine("Swapping is not possible"); } } //display() will display all the nodes present in the list public void display() { //Node current will point to head Node<T> current = head; if(head == null) { Console.WriteLine("List is empty"); return; } while(current != null) { //Prints each node by incrementing pointer Console.Write(current.data + " "); current = current.next; } Console.WriteLine(); } } public static void Main() { SwapNodes<int> sList = new SwapNodes<int>(); //Add nodes to the list sList.addNode(1); sList.addNode(2); sList.addNode(3); sList.addNode(4); sList.addNode(5); Console.WriteLine("Original list: "); sList.display(); //Swaps the node 2 with node 5 sList.swap(2,5); Console.WriteLine("List after swapping nodes: "); sList.display(); } } Output: Original list: 1 2 3 4 5 List after swapping nodes: 1 5 3 4 2 PHP<!DOCTYPE html> <html> <body> <?php //Represent a node of singly linked list class Node{ public $data; public $next; function __construct($data){ $this->data = $data; $this->next = NULL; } } class SwapNodes{ //Represent the head and tail of the singly linked list public $head; public $tail; function __construct(){ $this->head = NULL; $this->tail = NULL; } //addNode() will add a new node to the list function addNode($data) { //Create a new node $newNode = new Node($data); //Checks if the list is empty if($this->head == NULL) { //If list is empty, both head and tail will point to new node $this->head = $newNode; $this->tail = $newNode; } else { //newNode will be added after tail such that tail's next will point to newNode $this->tail->next = $newNode; //newNode will become new tail of the list $this->tail = $newNode; } } //swap() will swap the given two nodes function swap($n1, $n2){ $prevNode1 = null; $prevNode2 = null; $node1 = $this->head; $node2 = $this->head; //Checks if list is empty if($this->head == null) { return; } //If n1 and n2 are equal, then list will remain the same if($n1 == $n2) return; //Search for node1 while($node1 != null && $node1->data != $n1){ $prevNode1 = $node1; $node1 = $node1->next; } //Search for node2 while($node2 != null && $node2->data != $n2){ $prevNode2 = $node2; $node2 = $node2->next; } if($node1 != null && $node2 != null) { //If previous node to node1 is not null then, it will point to node2 if($prevNode1 != null) $prevNode1->next = $node2; else $this->head = $node2; //If previous node to node2 is not null then, it will point to node1 if($prevNode2 != null) $prevNode2->next = $node1; else $this->head = $node1; //Swaps the next nodes of node1 and node2 $temp = $node1->next; $node1->next = $node2->next; $node2->next = $temp; } else { print("Swapping is not possible <br>"); } } //display() will display all the nodes present in the list function display() { //Node current will point to head $current = $this->head; if($this->head == NULL) { print("List is empty <br>"); return; } while($current != NULL) { //Prints each node by incrementing pointer print($current->data . " "); $current = $current->next; } print("<br>"); } } $sList = new SwapNodes(); //Add nodes to the list $sList->addNode(1); $sList->addNode(2); $sList->addNode(3); $sList->addNode(4); $sList->addNode(5); print("Original list: <br>"); $sList->display(); //Swaps the node 2 with node 5 $sList->swap(2,5); print("List after swapping nodes: <br>"); $sList->display(); ?> </body> </html> Output: Original list: 1 2 3 4 5 List after swapping nodes: 1 5 3 4 2
Next Topic#
|