Find Middle Element in a Singly Linked List

Please go through Create a Singly Linked List in Java before proceeding further.

We will use two ways to get the Middle Node of the Singly Linked List.

1.  Traverse through the LinkedList and find the length(n). Then again traverse till n/2 and return the Node found at n/2.

2. Create two References

• slow reference->advance only one node per iteration
• fast reference -> advance 2 nodes in each iteration

When the fast reference reaches the end, the slow reference will be pointing to the Middle Node.

package com.java.datastructure;

public class SinglyLinkedList {
	
	private Node head;
	private Node tail;
	
	public void addToFirst(String data) {		
		  if(head == null) {
			  head = new Node(data, null);
			  tail = head;
		  }else {
			  Node newNode = new Node(data, head);
			  head = newNode;
		  }
		}
	
	public void addToLast(String data) {		
	  if(head == null) {
		  head = new Node(data, null);
		  tail = head;
	  }else {
		  Node newNode = new Node(data, null);
		  tail.setNext(newNode);
		  tail = newNode;
	  }
	}
	
	public void traverse() {
		if(head == null) {
			System.out.println("No elements in the SinglyLinkedList");
			return;
		}
		Node node = head;
		int i =0;
		while(node != null) {
			if( i > 0) {
				System.out.print(" ==> ");
			}
			System.out.print(node);
			node = node.getNext();
			i++;
		}
	}
	
	public Node middleNode() {
		int count =0;
		Node node = head;
		while(node != null) {
			node = node.getNext();
			count++;
		}
		int i=0;
		Node middleNode = head;
		while(i < count/2) {
			middleNode = middleNode.getNext();
			i++;
		}
		return middleNode;
	}
	
	public Node middleNodeInOneLoop() {
		Node slow = head;
		Node fast = head;
		while(fast !=null && fast.getNext() != null) {
			fast = fast.getNext().getNext();
			slow = slow.getNext();
		}
		return slow;
	}
	
	public static void main(String[] args) {
		SinglyLinkedList linkedList = new SinglyLinkedList();
		linkedList.addToLast("Rochit");
		linkedList.addToLast("Gyan");
		linkedList.addToLast("Praveen");
		linkedList.addToFirst("Vivek");
		linkedList.addToFirst("Panda");
		linkedList.addToFirst("Satya");
		linkedList.addToFirst("Amit");
		linkedList.traverse();
		System.out.println("");
		System.out.println("Middle Node in 1.5 Loop:"+linkedList.middleNode());
		System.out.println("Middle Node in One Loop:"+linkedList.middleNodeInOneLoop());
	}
}
class Node{
	public String getData() {
		return data;
	}
	public Node getNext() {
		return next;
	}
	public Node(String data, Node next) {
		this.data = data;
		this.next = next;
	}
	public void setData(String data) {
		this.data = data;
	}
	public void setNext(Node next) {
		this.next = next;
	}
	@Override
	public String toString() {
		if(next != null) {
		return "Node [data=" + data + ", next=" + next.getData() + "]";
		}
		return "Node [data=" + data + ", next=" + next + "]";
	}
	private String data;
	private Node next;
}

Output

Node [data=Amit, next=Satya] ==> Node [data=Satya, next=Panda] ==> Node [data=Panda, next=Vivek] ==> Node [data=Vivek, next=Rochit] ==> Node [data=Rochit, next=Gyan] ==> Node [data=Gyan, next=Praveen] ==> Node [data=Praveen, next=null]
Middle Node in 1.5 Loop:Node [data=Vivek, next=Rochit]
Middle Node in One Loop:Node [data=Vivek, next=Rochit]