CC-7 : Partition/ re-arrange a SingleLinkedList around a given input number.

Description:

Given an input SingleLinkedList, and an input number N, re-arrange the SingleLinkedList, so that nodes with data value lesser than N occur before node with datavalue N in the SingleLinkedList and nodes with data value greater than N occur after N in the SingleLinkedList.

Test cases and expected outputs:

Input Parameters	Expected outputs
8->44->7->3->11->2->17->15->12->19 Partition Value is : 15	8->7->3->11->2->12->15->44->17->19
8->44->7->3->11->2->17->11->12->19 Partition Value is : 2	2->8->44->7->3->11->17->11->12->19
8->44->7->3->11->2->17->11->12->19 Partition Value is : 44	8->7->3->11->2->17->11->12->19->44

Pseudocode:

We will partition the input SingleLinkedList into 3 separate SingleLinkedLists P1,P2and P3.

Traverse through each node of input SingleLinkedList:

If the currentNode’s data value is less than N, add currentNode to SIngleLinkedList P1.

If the currentNode’s data value is equal to N, add currentNode to SIngleLinkedList P2.

If the currentNode’s data value is greater than N, add currentNode to SIngleLinkedList P3.

Join P1 and P2 and P3.

Code:

public SingleLinkedList singleLinkedListPartition(SingleLinkedList singleLinkedList, int partition) throws Exception{
	if (singleLinkedList.getFirstNode()==null) { return singleLinkedList;}
	SingleLinkedListNode firstNodeP1=null; SingleLinkedListNode lastNodeP1=null;
	SingleLinkedListNode firstNodeP2=null; SingleLinkedListNode lastNodeP2=null;
	SingleLinkedListNode firstNodeP3=null; SingleLinkedListNode lastNodeP3=null;
	SingleLinkedListNode currentNode=singleLinkedList.getFirstNode();
	while (currentNode !=null) {
		if (currentNode.getNodeData() < partition) {
			if (firstNodeP1==null) {
				firstNodeP1=currentNode;
				lastNodeP1=currentNode;
			}else {
				lastNodeP1.setNextNode(currentNode);
				lastNodeP1=currentNode;
			}
		}else {if (currentNode.getNodeData() == partition) {
			if (firstNodeP2==null) {
				firstNodeP2=currentNode;
				lastNodeP2=currentNode;
			}else {
				lastNodeP2.setNextNode(currentNode);
				lastNodeP2=currentNode;
			}
			} else {	if (currentNode.getNodeData() > partition) {
				if (firstNodeP3==null) {
					firstNodeP3=currentNode;
					lastNodeP3=currentNode;
				}else {
					lastNodeP3.setNextNode(currentNode);
					lastNodeP3=currentNode;
				}	
			}
		}
		}
		currentNode=currentNode.getNextNode();
	}
	if (lastNodeP1 != null) {
		if (firstNodeP2 != null) {
			lastNodeP1.setNextNode(firstNodeP2);
			lastNodeP2.setNextNode(firstNodeP3);
			}else {
				lastNodeP1.setNextNode(firstNodeP3);
			}
	}else {if (lastNodeP2 != null) {
		lastNodeP2.setNextNode(firstNodeP3);
	}
	}		
	if (firstNodeP1!=null) {
		singleLinkedList.setFirstNode(firstNodeP1);
	}else { if (firstNodeP2 !=null) {
		singleLinkedList.setFirstNode(firstNodeP2);
	}else {
		singleLinkedList.setFirstNode(firstNodeP3);
	}
	}		
	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 SingleLinkedListPartition {
	
public SingleLinkedList singleLinkedListPartition(SingleLinkedList singleLinkedList, int partition) throws Exception{
	if (singleLinkedList.getFirstNode()==null) { return singleLinkedList;}
	SingleLinkedListNode firstNodeP1=null; SingleLinkedListNode lastNodeP1=null;
	SingleLinkedListNode firstNodeP2=null; SingleLinkedListNode lastNodeP2=null;
	SingleLinkedListNode firstNodeP3=null; SingleLinkedListNode lastNodeP3=null;
	SingleLinkedListNode currentNode=singleLinkedList.getFirstNode();
	while (currentNode !=null) {
		if (currentNode.getNodeData() < partition) {
			if (firstNodeP1==null) {
				firstNodeP1=currentNode;
				lastNodeP1=currentNode;
			}else {
				lastNodeP1.setNextNode(currentNode);
				lastNodeP1=currentNode;
			}
		}else {if (currentNode.getNodeData() == partition) {
			if (firstNodeP2==null) {
				firstNodeP2=currentNode;
				lastNodeP2=currentNode;
			}else {
				lastNodeP2.setNextNode(currentNode);
				lastNodeP2=currentNode;
			}
			} else {	if (currentNode.getNodeData() > partition) {
				if (firstNodeP3==null) {
					firstNodeP3=currentNode;
					lastNodeP3=currentNode;
				}else {
					lastNodeP3.setNextNode(currentNode);
					lastNodeP3=currentNode;
				}	
			}
		}
		}
		currentNode=currentNode.getNextNode();
	}
	if (lastNodeP1 != null) {
		if (firstNodeP2 != null) {
			lastNodeP1.setNextNode(firstNodeP2);
			lastNodeP2.setNextNode(firstNodeP3);
			}else {
				lastNodeP1.setNextNode(firstNodeP3);
			}
	}else {if (lastNodeP2 != null) {
		lastNodeP2.setNextNode(firstNodeP3);
	}
	}		
	if (firstNodeP1!=null) {
		singleLinkedList.setFirstNode(firstNodeP1);
	}else { if (firstNodeP2 !=null) {
		singleLinkedList.setFirstNode(firstNodeP2);
	}else {
		singleLinkedList.setFirstNode(firstNodeP3);
	}
	}		
	return singleLinkedList;
}
	
	
	
    
public static void main(String[] args) {
	SingleLinkedList retVal;
	
	try {
	SingleLinkedListPartition singleLinkedListPartition=new SingleLinkedListPartition();
	SingleLinkedList singleLinkedList=singleLinkedListPartition.new SingleLinkedList();
	singleLinkedList.addLast(8);
	singleLinkedList.addLast(44);
	singleLinkedList.addLast(7);
	singleLinkedList.addLast(3);
	singleLinkedList.addLast(11);
	singleLinkedList.addLast(2);
	singleLinkedList.addLast(17);
	singleLinkedList.addLast(15);
	singleLinkedList.addLast(12);
	singleLinkedList.addLast(19);
	singleLinkedList.printSingleLinkList();
	int partition =15;
	System.out.println("Partition Value is : "+ 15);
	
	retVal=singleLinkedListPartition.singleLinkedListPartition(singleLinkedList,partition);
	retVal.printSingleLinkList();
	
	singleLinkedList=singleLinkedListPartition.new SingleLinkedList();
	singleLinkedList.addLast(8);
	singleLinkedList.addLast(44);
	singleLinkedList.addLast(7);
	singleLinkedList.addLast(3);
	singleLinkedList.addLast(11);
	singleLinkedList.addLast(2);
	singleLinkedList.addLast(17);
	singleLinkedList.addLast(11);
	singleLinkedList.addLast(12);
	singleLinkedList.addLast(19);
	singleLinkedList.printSingleLinkList();
	partition =2;
	System.out.println("Partition Value is : "+ 2);
	singleLinkedListPartition=new SingleLinkedListPartition();
	retVal=singleLinkedListPartition.singleLinkedListPartition(singleLinkedList,partition);
	retVal.printSingleLinkList();
	
	singleLinkedList=singleLinkedListPartition.new SingleLinkedList();
	singleLinkedList.addLast(8);
	singleLinkedList.addLast(44);
	singleLinkedList.addLast(7);
	singleLinkedList.addLast(3);
	singleLinkedList.addLast(11);
	singleLinkedList.addLast(2);
	singleLinkedList.addLast(17);
	singleLinkedList.addLast(11);
	singleLinkedList.addLast(12);
	singleLinkedList.addLast(19);
	singleLinkedList.printSingleLinkList();
	partition =44;
	System.out.println("Partition Value is : "+ 44);
	singleLinkedListPartition=new SingleLinkedListPartition();
	retVal=singleLinkedListPartition.singleLinkedListPartition(singleLinkedList,partition);
	retVal.printSingleLinkList();
	
	
				
	singleLinkedList=singleLinkedListPartition.new SingleLinkedList();
	singleLinkedList.addLast(8);
	singleLinkedList.printSingleLinkList();
	partition =8;
	System.out.println("Partition Value is : "+ 8);
	singleLinkedListPartition=new SingleLinkedListPartition();
	retVal=singleLinkedListPartition.singleLinkedListPartition(singleLinkedList,partition);
	retVal.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;
	}
	
	
}	
	

}