CC-3 : Delete middle node of a SingleLinkedList.

Description:

If SingleLinkedList has odd count of nodes n, then node at position (n/2+1) should be deleted.If SingleLinkedList has even count of nodes n, then it has 2 middle nodes, in this case delete node at position (n/2+1).If SingleLinkedList has only one node, delete the node.

Test cases and expected outputs:

Input Parameters	Expected outputs
6 -> 11 -> 7 -> 4 -> 23 -> 9	6 -> 11 -> 7 -> 23 -> 9
36 -> 51 -> 27 -> 55 -> 44 -> 23 -> 33	36 -> 51 -> 27 -> 44 -> 23 -> 33
33	null

Pseudocode:

Create 2 pointers and use these to navigate to the end of the SingleLinkedList using nextNode links:

CurrentNode : this pointer is updated to nextNode in each step (i.e it will iterate Node1->Node-2->Node3 and so on).

CurrentNode2xspeed: this pointer is updated to next to nextNode in each iteration (i.e it will iterate to Node1->Node3->Node5 and so on).

Both above pointers should be incremented in the same loop.

When CurrentNode2xspeed reaches end of the SingleLinkedList, at that time currentNode will be pointing to middle of SingleLinkedList. Now we can use currentNode pointer to delete the node at the middle of the SingleLinkedList.

Handle following special cases in your code:

SingleLinkedList empty.

SingleLinkedList having only one node.

SingleLinkedList having even number of nodes.

SingleLinkedList having odd number of nodes.

Code:

public SingleLinkedList deleteMiddleNode(SingleLinkedList singleLinkedList) throws Exception{
	if (singleLinkedList.getFirstNode()==null) { return null;	}
	SingleLinkedListNode currentNode=singleLinkedList.getFirstNode();
	SingleLinkedListNode currentNode2xspeed=singleLinkedList.getFirstNode();
	int numberOfNodesInList=1;
	int idx=0;
	while (currentNode2xspeed.getNextNode()!= null)	{
		if (currentNode2xspeed.getNextNode().getNextNode()!=null) {
			currentNode2xspeed=currentNode2xspeed.getNextNode().getNextNode();
			numberOfNodesInList=numberOfNodesInList+2;
		}
		else {
			currentNode2xspeed=currentNode2xspeed.getNextNode();
			numberOfNodesInList=numberOfNodesInList+1;
		}
		currentNode=currentNode.getNextNode();		
		idx++;
	}
	singleLinkedList.removeAtPos(idx);
	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 SingleLinkedListDeleteMiddleNode {
	
public SingleLinkedList deleteMiddleNode(SingleLinkedList singleLinkedList) throws Exception{
	if (singleLinkedList.getFirstNode()==null) { return null;	}
	SingleLinkedListNode currentNode=singleLinkedList.getFirstNode();
	SingleLinkedListNode currentNode2xspeed=singleLinkedList.getFirstNode();
	int numberOfNodesInList=1;
	int idx=0;
	while (currentNode2xspeed.getNextNode()!= null)	{
		if (currentNode2xspeed.getNextNode().getNextNode()!=null) {
			currentNode2xspeed=currentNode2xspeed.getNextNode().getNextNode();
			numberOfNodesInList=numberOfNodesInList+2;
		}
		else {
			currentNode2xspeed=currentNode2xspeed.getNextNode();
			numberOfNodesInList=numberOfNodesInList+1;
		}
		currentNode=currentNode.getNextNode();		
		idx++;
	}
	singleLinkedList.removeAtPos(idx);
	return singleLinkedList;		
}
	
	
	
    
public static void main(String[] args) {
	SingleLinkedList retVal;
		
	try {
	SingleLinkedListDeleteMiddleNode singleLinkedListDeleteMiddleNode=new SingleLinkedListDeleteMiddleNode();
	SingleLinkedList singleLinkedList=singleLinkedListDeleteMiddleNode.new SingleLinkedList();
	singleLinkedList.addFirst(9);
	singleLinkedList.addFirst(23);
	singleLinkedList.addFirst(4);
	singleLinkedList.addFirst(7);
	singleLinkedList.addFirst(11);
	singleLinkedList.addFirst(6);
	singleLinkedList.printSingleLinkList();
	retVal=singleLinkedListDeleteMiddleNode.deleteMiddleNode(singleLinkedList);
	retVal.printSingleLinkList();
			
	singleLinkedList=singleLinkedListDeleteMiddleNode.new SingleLinkedList();
	singleLinkedList.addFirst(33);
	singleLinkedList.addFirst(23);
	singleLinkedList.addFirst(44);
	singleLinkedList.addFirst(55);
	singleLinkedList.addFirst(27);
	singleLinkedList.addFirst(51);
	singleLinkedList.addFirst(36);
	singleLinkedList.printSingleLinkList();
	singleLinkedListDeleteMiddleNode=new SingleLinkedListDeleteMiddleNode();
	retVal=singleLinkedListDeleteMiddleNode.deleteMiddleNode(singleLinkedList);
	retVal.printSingleLinkList();
			
	singleLinkedList=singleLinkedListDeleteMiddleNode.new SingleLinkedList();
	singleLinkedList.addFirst(33);
	singleLinkedList.printSingleLinkList();
	singleLinkedListDeleteMiddleNode=new SingleLinkedListDeleteMiddleNode();
	retVal=singleLinkedListDeleteMiddleNode.deleteMiddleNode(singleLinkedList);
	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;
	}
	
	
}	
	
	
}