Find Middle Element of Linked List in Java

In this article, we’ll learn how to find middle element of a linked list using multiple approach in Java.

Approach 1: Keep track of the LinkedList size

In first approach, we can keep track of size of the linked list. We can have a size counter initialized as zero. Increase or decrease the counter by 1, on addition or deletion of nodes from linked list respectively.

In this case, middle element’s index will be (size-1)/2

class LinkedList<T> {

	Node<T> head = null;
	int size = 0;

	public Node<T> get(int index) {
		Node<T> node = head;
		// get by index
		return node;
	}

	public void add(T t) {
		// add element
		size++;
	}

	public void delete(int index) {
		// delete element
		size--;
	}

	public void findMiddleElement() {
		get((size - 1) / 2);
	}
}

Approach 2: Traverse the LinkedList to find size

Sometime we have given only the head node of the linked list and no information about the size.

In simplest approach, we can traverse through whole linked list starting from head till end to find the size of the linked list.

In this case, middle element’s index will be (size()-1)/2

class LinkedList<T> {

	Node<T> head = null;

	public Node<T> get(int index) {
		Node<T> node = head;
		// get by index
		return node;
	}

	public int size() {
		Node<T> node = head;
		int size = 1;
		while (node.getNext() != null) {
			node = node.getNext();
			size++;
		}
		return size;
	}

	public void findMiddleElement() {
		get((size() - 1) / 2);
	}
}

If linked list is having n elements, then this approach requires n iteration to get size and n/2 iteration to get middle elements.
Total iteration is (n + n/2)

Approach 3: Fast and Slow pointers

This approach is also applicable when size of the linked list is unknown and only head node is given.

In this approach, we iterate through the linked list using two pointers. Fast pointer jumps 2 nodes in each iteration, and the slow pointer jumps only one node per iteration.

When the fast pointer reaches the end of the list, the slow pointer will be at the middle element.

class LinkedList<T> {

	Node<T> head = null;

	public Node<T> findMiddleElement() {
		Node<T> slow = head;
		Node<T> fast = head;
		while (fast != null && fast.getNext() != null) {
			fast = fast.getNext().getNext();
			slow = slow.getNext();
		}
		return slow;
	}
}

This is best approach when size is unknown as we are able to find the middle elements in just n/2 iterations.

Summary

We learned that it is always good to keep track of linked list size to find the middle element. Moreover, when size of the linked list is unknown then Fast and slow pointer approach is the way to go.