CC-5 : Merge 2 sorted SingleLinkedLists into a single sorted SingleLinkedList.

Description:

Given two sorted SingleLinkedLists, write and test code merges the same in to single sorted SingleLinkedList.

Test cases and expected outputs:

Input Parameters	Expected outputs
22 -> 44 -> 77 -> 99 20 -> 40 -> 70 -> 90	20 -> 22 -> 40 -> 44 -> 70 -> 77 -> 90 -> 99
1 -> 2 -> 3 -> 4 5 -> 5 -> 6 -> 7	1 -> 2 -> 3 -> 4 -> 5 -> 5 -> 6 -> 7
10 -> 21 -> 37 -> 44 Empty	10 -> 21 -> 37 -> 44

Pseudocode:

Two SingleLinkedLists S1 andS2 with sorted integer data are received as input parameters.

Create a SingleLinkedList named merged to hold the sorted merged SingleLinkedList.

Use a single while loop to iterate through both input SingleLinkedLists S1 andS2 at the same time, in each iteration:

Compare the node data of current nodes from S1 and S2.

Add the node with lesser value to merged SingleLinkedList.

Move to nextNode only for the input SingleLInkedList that’s node was moved to merged.

Return the merged SingleLinkedList.

Code:

public SingleLinkedList singleLinkListMergeLists(SingleLinkedList s1, SingleLinkedList s2) throws Exception{
	SingleLinkedListNode s1CurrNode=s1.getFirstNode();SingleLinkedListNode s2CurrNode=s2.getFirstNode();
	int s1Data=Integer.MAX_VALUE; int s2Data=Integer.MAX_VALUE;
	SingleLinkedList merged=new SingleLinkedList();
	while ((s1CurrNode != null)||(s2CurrNode !=null)) {
		s1Data=Integer.MAX_VALUE; s2Data=Integer.MAX_VALUE;
		if (s1CurrNode != null) {
			s1Data=s1CurrNode.getNodeData();
		}
		if (s2CurrNode != null) {
			s2Data=s2CurrNode.getNodeData();
		}
		if (s1Data < s2Data) {
			merged.addLast(s1Data);	
			s1CurrNode=s1CurrNode.getNextNode();
		}else {
			merged.addLast(s2Data);
			s2CurrNode=s2CurrNode.getNextNode();
		}		
	}
	return merged;
}

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 SingleLinkedMergeLists {
	
public SingleLinkedList singleLinkListMergeLists(SingleLinkedList s1, SingleLinkedList s2) throws Exception{
	SingleLinkedListNode s1CurrNode=s1.getFirstNode();SingleLinkedListNode s2CurrNode=s2.getFirstNode();
	int s1Data=Integer.MAX_VALUE; int s2Data=Integer.MAX_VALUE;
	SingleLinkedList merged=new SingleLinkedList();
	while ((s1CurrNode != null)||(s2CurrNode !=null)) {
		s1Data=Integer.MAX_VALUE; s2Data=Integer.MAX_VALUE;
		if (s1CurrNode != null) {
			s1Data=s1CurrNode.getNodeData();
		}
		if (s2CurrNode != null) {
			s2Data=s2CurrNode.getNodeData();
		}
		if (s1Data < s2Data) {
			merged.addLast(s1Data);	
			s1CurrNode=s1CurrNode.getNextNode();
		}else {
			merged.addLast(s2Data);
			s2CurrNode=s2CurrNode.getNextNode();
		}		
	}
	return merged;
}

    
public static void main(String[] args) {
	try {
	SingleLinkedMergeLists mergeLists=new SingleLinkedMergeLists();
	SingleLinkedList s1=mergeLists.new SingleLinkedList();
	s1.addFirst(99);
	s1.addFirst(77);
	s1.addFirst(44);
	s1.addFirst(22);
	s1.printSingleLinkList();
	SingleLinkedList s2=mergeLists.new SingleLinkedList();
	s2.addFirst(90);
	s2.addFirst(70);
	s2.addFirst(40);
	s2.addFirst(20);
	s2.printSingleLinkList();
	
	SingleLinkedList merged=mergeLists.new SingleLinkedList();
	merged=mergeLists.singleLinkListMergeLists(s1, s2);
	System.out.println("Mergedlist:");
	merged.printSingleLinkList();
			
	s1=mergeLists.new SingleLinkedList();
	s1.addFirst(4);
	s1.addFirst(3);
	s1.addFirst(2);
	s1.addFirst(1);
	s1.printSingleLinkList();
	s2=mergeLists.new SingleLinkedList();
	s2.addFirst(7);
	s2.addFirst(6);
	s2.addFirst(5);
	s2.addFirst(5);
	s2.printSingleLinkList();
	mergeLists=new SingleLinkedMergeLists();
	merged=mergeLists.singleLinkListMergeLists(s1, s2);
	System.out.println("Mergedlist:");
	merged.printSingleLinkList();
			
			
	s1=mergeLists.new SingleLinkedList();
	s1.addFirst(44);
	s1.addFirst(37);
	s1.addFirst(21);
	s1.addFirst(10);
	s1.printSingleLinkList();
	s2=mergeLists.new SingleLinkedList();
	s2.printSingleLinkList();
	mergeLists=new SingleLinkedMergeLists();
	merged=mergeLists.singleLinkListMergeLists(s1, s2);
	System.out.println("Mergedlist:");
	merged.printSingleLinkList();
			
			
	s1=mergeLists.new SingleLinkedList();
	s1.printSingleLinkList();
	s2=mergeLists.new SingleLinkedList();
	s2.addFirst(7);
	s2.addFirst(6);
	s2.addFirst(5);
	s2.addFirst(5);
	s2.printSingleLinkList();
	mergeLists=new SingleLinkedMergeLists();
	merged=mergeLists.singleLinkListMergeLists(s1, s2);
	System.out.println("Mergedlist:");
	merged.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;
	}
	
	
}	
		
	
}