Question

Write a program to swap mth and nth elements of a linked list.

User should give input.

Answer 1

import java.util.Scanner;

public class Main {
  
//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;
  
//push() will add a new node to the list
public void push(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;
}
}
public int getElementAtThatNode(int index)
{
Node current = head;
int count = 0; /* index of Node we are
currently looking at */
while (current != null)
{
if (count == index)
return current.data;
count++;
current = current.next;
}
  
/* if we get to this line, the caller was asking
for a non-existent element so we assert fail */
assert(false);
return 0;
}
//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");
}
}
  
//printList() will display all the nodes present in the list
public void printList() {
//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) {
Scanner myObj = new Scanner(System.in);
Main sList = new Main();
System.out.println("How many nodes you want to add in linked list ?:");
int n1 = myObj.nextInt();
//Add nodes to the list
for(int i = 0 ; i< n1; i ++){
System.out.println("Enter your node "+(i+1)+ ":");
int myNode = myObj.nextInt();
sList.push(myNode);
}
System.out.println("\nOriginal list: ");
sList.printList();
System.out.println("Enter node 1 with you want to swap:");
int m = myObj.nextInt();
System.out.println("Enter node 2 with you want to swap:");
int n = myObj.nextInt();
  
m = sList.getElementAtThatNode(m-1);
n = sList.getElementAtThatNode(n-1);
//Swaps the node m with n.
sList.swap(m,n);
  
System.out.println("\nList after swapping nodes: ");
sList.printList();
}
}