CC-6 : Swap adjacent nodes of SingleLinkedList.

Description:

Given an input SingleLinkedList, traverse the list 2 nodes at a time. Swap the current 2 nodes and then pick up the next 2 nodes and so on till end of the SingleLinkedList is reached.

Test cases and expected outputs:

Input Parameters	Expected outputs
2->1->4->3->6->5->10	1->2->3->4->5->6->10
10->11->12->13->14->15	11->10->13->12->15->14

Pseudocode:

Traverse the input SingleLinkedList starting from its firstNode using a do-while loop till end of SingleLinkedList is reached:

Swap the currentnode and its nextNode.

Correct the linkages with nodes before current node and after nextNode.

Handle cases of odd number of nodes in SingleLinkedList , due to which last node is not part of pair of nodes.

Code:

public SingleLinkedList singleLinkListSwapNodes(SingleLinkedList singleLinkedList) throws Exception{
	if ((singleLinkedList.getFirstNode()== null)||(singleLinkedList.getSize()==1)) 
		{return singleLinkedList;}
	SingleLinkedListNode currentNode=singleLinkedList.getFirstNode();
	SingleLinkedListNode prevNode=null; 
	SingleLinkedListNode nextNode=null; 
	do {
		nextNode=currentNode.getNextNode();
		if (nextNode==null) {return singleLinkedList;}
		if (prevNode != null) {
			prevNode.setNextNode(nextNode);
		}
	    if (currentNode==singleLinkedList.getFirstNode()) 
	    	{singleLinkedList.setFirstNode(nextNode);}
		currentNode.setNextNode(nextNode.getNextNode());
		nextNode.setNextNode(currentNode);
		prevNode=currentNode;
		currentNode=currentNode.getNextNode();		
	} while(currentNode != null);
	return singleLinkedList;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SingleLinkedListSwapNodes {
	
public SingleLinkedList singleLinkListSwapNodes(SingleLinkedList singleLinkedList) throws Exception{
	if ((singleLinkedList.getFirstNode()== null)||(singleLinkedList.getSize()==1)) 
		{return singleLinkedList;}
	SingleLinkedListNode currentNode=singleLinkedList.getFirstNode();
	SingleLinkedListNode prevNode=null; 
	SingleLinkedListNode nextNode=null; 
	do {
		nextNode=currentNode.getNextNode();
		if (nextNode==null) {return singleLinkedList;}
		if (prevNode != null) {
			prevNode.setNextNode(nextNode);
		}
	    if (currentNode==singleLinkedList.getFirstNode()) 
	    	{singleLinkedList.setFirstNode(nextNode);}
		currentNode.setNextNode(nextNode.getNextNode());
		nextNode.setNextNode(currentNode);
		prevNode=currentNode;
		currentNode=currentNode.getNextNode();		
	} while(currentNode != null);
	return singleLinkedList;
}
	

    
public static void main(String[] args) {
				
	try {
	SingleLinkedListSwapNodes singleLinkedListSwapNodes=new SingleLinkedListSwapNodes();
	SingleLinkedList singleLinkedList=singleLinkedListSwapNodes.new SingleLinkedList();
	singleLinkedList.addLast(2);
	singleLinkedList.addLast(1);
	singleLinkedList.addLast(4);
	singleLinkedList.addLast(3);
	singleLinkedList.addLast(6);
	singleLinkedList.addLast(5);
	singleLinkedList.addLast(10);
	singleLinkedList.printSingleLinkList();
	System.out.println("Swapping nodes");
	singleLinkedListSwapNodes.singleLinkListSwapNodes(singleLinkedList);
	singleLinkedList.printSingleLinkList();
			
			
	singleLinkedList=singleLinkedListSwapNodes.new SingleLinkedList();
	singleLinkedList.addLast(10);
	singleLinkedList.addLast(11);
	singleLinkedList.addLast(12);
	singleLinkedList.addLast(13);
	singleLinkedList.addLast(14);
	singleLinkedList.addLast(15);
	singleLinkedList.printSingleLinkList();
	System.out.println("Swapping nodes");
	singleLinkedListSwapNodes.singleLinkListSwapNodes(singleLinkedList);
	singleLinkedList.printSingleLinkList();
		    
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	}
				
}


class SingleLinkedList {
	
private SingleLinkedListNode firstNode=null;

public SingleLinkedListNode getFirstNode() {
	return firstNode;
}

public void setFirstNode(SingleLinkedListNode firstNode) {
	this.firstNode = firstNode;
}

public boolean addLast(int data){
	SingleLinkedListNode node=new SingleLinkedListNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setNextNode(null);
		return true;
	}
	else {
		SingleLinkedListNode currentNode=firstNode;
		while (currentNode.getNextNode()!=null) {currentNode=currentNode.getNextNode();}
			currentNode.setNextNode(node);
			node.setNextNode(null);
			return true;			
	}
}
	
public boolean addFirst(int data){
	SingleLinkedListNode node=new SingleLinkedListNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setNextNode(null);
		return true;
	}
	else {
		node.setNextNode(firstNode);
		firstNode=node; 
		return true;
		
	}
}
	
public boolean add(int data, int pos)
{	
	int size=getSize();
	if ((pos<0) || (pos > size)) { return false;}
	if (pos==0) {
		addFirst(data);
		return true;
	}
	if (pos==size) {
		addLast(data);
		return true;
	}
	SingleLinkedListNode node=new SingleLinkedListNode();
	node.setNodeData(data);
  	SingleLinkedListNode currentNode=firstNode;
  	SingleLinkedListNode prevNode=null;
  	int idx=0;
  	while (currentNode !=null) {
  		if ((idx==pos)){
  	  		node.setNextNode(prevNode.getNextNode());
  	  		prevNode.setNextNode(node);
  	  		return true;
  	  	}
  		prevNode=currentNode;
  		currentNode=currentNode.getNextNode();
  		idx++;
  	}  	
  	return false;  	
 }	

public int getSize() {
	SingleLinkedListNode currentNode=firstNode;
  	int idx=0;
  	while (currentNode !=null) {
  		currentNode=currentNode.getNextNode();
  		idx++;
  	}
  	return idx;
}

public boolean removeFirst() {
	if (firstNode == null) { return false; }
	if (firstNode.getNextNode()==null) {
		firstNode=null; 
		return true;
	}
	firstNode=firstNode.getNextNode();
	return true;
}

public boolean removeLast() {
	if (firstNode == null) { return false; }
	SingleLinkedListNode currentNode=firstNode;
	SingleLinkedListNode prevNode=null;
	while (currentNode !=null) {
		if (currentNode.getNextNode()==null) {
			if (prevNode==null) {
				firstNode=null;
				return true;
			}
  			prevNode.setNextNode(null);
  			return true;
		}
		prevNode=currentNode;
  		currentNode=currentNode.getNextNode();    		
  	}	
	return false;
}

public boolean remove(int data){	
	SingleLinkedListNode currentNode=firstNode;
  	SingleLinkedListNode prevNode=null;
  	while (currentNode !=null) {
  		if (currentNode.getNodeData() == data) {
  			if (prevNode==null) {
  				removeFirst();
  				return true;
  			}
  			if (currentNode.getNextNode()==null) {
  				removeLast();
  				return true;
  			}
  			prevNode.setNextNode(currentNode.getNextNode());
  			return true;
  		}
  		prevNode=currentNode;
  		currentNode=currentNode.getNextNode();  		
  	}  	
  	return false;  	
 }	

public boolean removeAtPos(int pos){	
	
	SingleLinkedListNode currentNode=firstNode;
  	SingleLinkedListNode prevNode=null;
  	int idx=0;
  	while (currentNode !=null) {
  		if (idx==pos) {
  			if (prevNode==null) {
  				removeFirst();
  				return true;
  			}
  			if (currentNode.getNextNode()==null) {
  				removeLast();
  				return true;
  			}
  			prevNode.setNextNode(currentNode.getNextNode());
  			return true;
  		}
  		prevNode=currentNode;
  		currentNode=currentNode.getNextNode();  
  		idx++;
  	}  	
  	return false;  	  	
 }	

public int get(int idx) {
	SingleLinkedListNode currentNode=firstNode;
  	int currIdx=0;
  	while (currentNode !=null) {
  		if (currIdx==idx) {return currentNode.getNodeData();}
  		currentNode=currentNode.getNextNode();
  		currIdx++;
  	}
  	return Integer.MIN_VALUE;
}

public void traverse() {
	SingleLinkedListNode currentNode=firstNode;
	while (currentNode !=null) {
  		System.out.println(currentNode.getNodeData());
  		currentNode=currentNode.getNextNode();
  	}
}

			
	// print SingleLinkList
    public void printSingleLinkList() throws Exception    {
    	// Case 1: The Linked list is empty !!
    	if (firstNode == null) { System.out.println("Linked list empty"); return; }
    	// Case 2: Print LinkedList node by node
		SingleLinkedListNode currentNode=firstNode;
		System.out.println();
		System.out.println("*********************************************************************");
		System.out.print("SingleLinkedList nodes: ");
		do  {
			    System.out.print(currentNode.getNodeData());
			    if (currentNode.getNextNode() != null)  System.out.print(" -> ");
				currentNode=currentNode.getNextNode();
				
			} while( currentNode != null);
		
			System.out.println();
			System.out.println("*********************************************************************");
			System.out.println();
			Thread.sleep(2000);
			;
			return;
	}
}	

	
class SingleLinkedListNode  {
	
	private SingleLinkedListNode nextNode=null;
		
	//This is the data stored by Linked list. Replace it by String, array , or any other datatype as per need
	private int nodeData=0;
	

	public SingleLinkedListNode getNextNode() {
		return nextNode;
	}
	public void setNextNode(SingleLinkedListNode nextNode) {
		this.nextNode = nextNode;
	}

	
	public int getNodeData() {
		return nodeData;
	}
	public void setNodeData(int nodeData) {
		this.nodeData = nodeData;
	}
	
	
}	
	
}