Algorithms

Find the middle element in a linked list

In this article, we will discuss how to find the middle element in a linked list. A linked list has several nodes, and each node in the list has the content and a pointer to the next node in the list. It does not store any pointer to the previous node. To store a single linked list, only the pointer to the first node in that list must be stored. The last node in a single linked list points to nothing.

In our previous article, we have discussed how to find the nth element in a singly linked list. This problem almost the same as the previous problem.

Find the middle element in a linked list

This is one of a very frequently asked question of the interview questions. There are several ways to explain the answer to this question. But interviewers ask for the efficient way to find the middle element in a linked list. Let’s see the data structure class of the linked list like the following:

package com.dineshonjava.algo;

/**
 * @author Dinesh.Rajput
 *
 */
public class Node {
	
	private Node next;
    private String data;
    
    public Node(String data) {
		super();
		this.data = data;
	}

	public boolean hasNext() {
        return next != null;
    }
 
    public void setNext(Node next) {
        this.next = next;
    }
    
    public Node getNext() {
		return next;
	}
    
	public String getData() {
		return data;
	}

	public String toString() {
        return this.data;
    }
}

Let’s see the following answers with several assumptions.

Assumption 1: Using Size of the Linked List

Step 1: First, traverse the whole linked list and find the size of the linked list.

Step 2: After finding a size of the linked again traverse to size/2 and locate size/2 element from the head of linkedlist.

Let’s see the following example:

/**
 * Find the middle element in a linked list using size of the linked list
 */
package com.dineshonjava.algo;

import java.util.Optional;

/**
 * @author Dinesh.Rajput
 *
 */
public class LinkedListTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		Node listNode = createLinkedList(11);
		System.out.println(findMiddleElementInLinkedList(listNode).get());
	}
	
	private static Node createLinkedList(int n) {
	    Node head = new Node("1");
	    Node current = head;
	 
	    for (int i = 2; i <= n; i++) {
	        Node newNode = new Node(String.valueOf(i));
	        current.setNext(newNode);
	        current = newNode;
	    }
	 
	    return head;
	}
	
	public static Optional findMiddleElementInLinkedList(Node head) {
	    if (head == null) {
	        return Optional.empty();
	    }
	 
	    Node current = head;
	    int size = 1;
	    while (current.hasNext()) {
	        current = current.getNext();
	        size++;
	    }
	 
	    current = head;
	    for (int i = 0; i < (size - 1) / 2; i++) {
	        current = current.getNext();
	    }
	 
	    return Optional.of(current.getData());
	}
}

You can run this code and find the middle element in a linked list using the size of the linked list. But in this approach the time complexity = time for finding the length of the list + time for locating the middle element. That means, total time complexity = o(n) + o(n) = o(n) and here the space complexity= o(1).

Let’s discuss another efficient way to find the middle element in a linked list without using the size of the linked list.

Assumptions 2: Without using Size of the Linked List

In this approach, we will traverse this linked list with the two pointers.

Step 1: Let’s assume two pointers as slowPointer and fastPointer and initialize them with the head.

Step 2: And slowPointer moves one by one node but teh fastPointer moves faster by two nodes.

Step 3: When the fastPointer will reach the end of the linked list then slowPoint will be at the middle node, is it point we are looking for.

Let’s see the code like the following:

/**
 * Find the middle element in a linked list without using size of the linked list
 */
package com.dineshonjava.algo;

import java.util.Optional;

/**
 * @author Dinesh.Rajput
 *
 */
public class LinkedListTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		Node listNode = createLinkedList(11);
		System.out.println(findMiddleElementInLinkedList(listNode).get());
	}
	
	private static Node createLinkedList(int n) {
	    Node head = new Node("1");
	    Node current = head;
	 
	    for (int i = 2; i <= n; i++) {
	        Node newNode = new Node(String.valueOf(i));
	        current.setNext(newNode);
	        current = newNode;
	    }
	 
	    return head;
	}
	
	private static Optional findMiddleElementInLinkedList(Node head) {
		if (head == null) {
	        return Optional.empty();
	    }
	 
	    Node slowPointer = head;
	    Node fastPointer = head;
	 
	    while (fastPointer.hasNext() && fastPointer.getNext().hasNext()) {
	        fastPointer = fastPointer.getNext().getNext();
	        slowPointer = slowPointer.getNext();
	    }
	    return Optional.ofNullable(slowPointer.getData());
	}
	
	

In this example, we can find the middle element in a linked list in a single traversal.

Hope, you have understood this solution for the above find the middle node from a linked list. Please share other solutions if you have. :).

Happy learning with us!!!.

Previous
Next
Dinesh Rajput

Dinesh Rajput is the chief editor of a website Dineshonjava, a technical blog dedicated to the Spring and Java technologies. It has a series of articles related to Java technologies. Dinesh has been a Spring enthusiast since 2008 and is a Pivotal Certified Spring Professional, an author of a book Spring 5 Design Pattern, and a blogger. He has more than 10 years of experience with different aspects of Spring and Java design and development. His core expertise lies in the latest version of Spring Framework, Spring Boot, Spring Security, creating REST APIs, Microservice Architecture, Reactive Pattern, Spring AOP, Design Patterns, Struts, Hibernate, Web Services, Spring Batch, Cassandra, MongoDB, and Web Application Design and Architecture. He is currently working as a technology manager at a leading product and web development company. He worked as a developer and tech lead at the Bennett, Coleman & Co. Ltd and was the first developer in his previous company, Paytm. Dinesh is passionate about the latest Java technologies and loves to write technical blogs related to it. He is a very active member of the Java and Spring community on different forums. When it comes to the Spring Framework and Java, Dinesh tops the list!

Share
Published by
Dinesh Rajput

Recent Posts

Strategy Design Patterns using Lambda

Strategy Design Patterns We can easily create a strategy design pattern using lambda. To implement…

2 years ago

Decorator Pattern using Lambda

Decorator Pattern A decorator pattern allows a user to add new functionality to an existing…

2 years ago

Delegating pattern using lambda

Delegating pattern In software engineering, the delegation pattern is an object-oriented design pattern that allows…

2 years ago

Spring Vs Django- Know The Difference Between The Two

Technology has emerged a lot in the last decade, and now we have artificial intelligence;…

2 years ago

TOP 20 MongoDB INTERVIEW QUESTIONS 2022

Managing a database is becoming increasingly complex now due to the vast amount of data…

2 years ago

Scheduler @Scheduled Annotation Spring Boot

Overview In this article, we will explore Spring Scheduler how we could use it by…

3 years ago