<p><img class="wp-image-4240 size-medium alignright" src="https://dineshonjava.com/wp-content/uploads/2018/09/maxresdefault-300x101.jpg" alt="Find the middle element in a linked list" width="300" height="101" />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.</p>
<p>In our previous article, we have discussed how to <strong><a href="https://dineshonjava.com/nth-node-from-the-end-of-a-singly-linked-list/">find the nth element in a singly linked list</a></strong>. This problem almost the same as the <strong><a href="https://dineshonjava.com/nth-node-from-the-end-of-a-singly-linked-list/">previous problem</a></strong>.</p>
<h2>Find the middle element in a linked list</h2>
<p>This is one of a very frequently asked question of the <strong><a href="https://dineshonjava.com/core-java-interview-questions/">interview questions</a></strong>. 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&#8217;s see the data structure class of the linked list like the following:</p>
<pre>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; 
 } 
} 
</pre>
<p>Let&#8217;s see the following answers with several assumptions.</p>
<h3>Assumption 1: Using Size of the Linked List</h3>
<p><strong>Step 1:</strong> First, traverse the whole linked list and find the size of the linked list.</p>
<p><strong>Step 2:</strong> After finding a size of the linked again traverse to size/2 and locate size/2 element from the head of linkedlist.</p>
<p>Let&#8217;s see the following example:</p>
<pre>/** 
 * 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()); 
	} 
} 
 
</pre>
<p>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 <em>time complexity = o(n) + o(n) = o(n)</em> and here the <em>space complexity= o(1).</em></p>
<p>Let&#8217;s discuss another efficient way to find the middle element in a linked list without using the size of the linked list.</p>
<h3>Assumptions 2: Without using Size of the Linked List</h3>
<p>In this approach, we will traverse this linked list with the two pointers.</p>
<p><strong>Step 1:</strong> Let&#8217;s assume two pointers as slowPointer and fastPointer and initialize them with the head.</p>
<p><strong>Step 2:</strong> And slowPointer moves one by one node but teh fastPointer moves faster by two nodes.</p>
<p><strong>Step 3:</strong> 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.</p>
<p>Let&#8217;s see the code like the following:</p>
<pre>/** 
 * 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()); 
	} 
	 
	 
</pre>
<p>In this example, we can find the middle element in a linked list in a single traversal.</p>
<p>Hope, you have understood this solution for the above find the middle node from a linked list. Please share other solutions if you have. :).</p>
<p>Happy learning with us!!!.</p>
<div align="center"><iframe style="width: 120px; height: 240px;" src="//ws-in.amazon-adsystem.com/widgets/q?ServiceVersion=20070822&;OneJS=1&;Operation=GetAdHtml&;MarketPlace=IN&;source=ac&;ref=qf_sp_asin_til&;ad_type=product_link&;tracking_id=dineshonjav06-21&;marketplace=amazon&;region=IN&;placement=1788299450&;asins=1788299450&;linkId=05b0146b0a85f4472697901e353dc276&;show_border=true&;link_opens_in_new_window=true&;price_color=333333&;title_color=0066c0&;bg_color=ffffff" frameborder="0" marginwidth="0" marginheight="0" scrolling="no"><br />
</iframe></div>
<div class="wp-post-navigation"> 
									 <div class="wp-post-navigation-pre"> 
									 <a href="https://dineshonjava.com/nth-node-from-the-end-of-a-singly-linked-list/">Previous</a> 
									 </div> 
									 <div class="wp-post-navigation-next"> 
									 <a href="https://dineshonjava.com/reverse-linked-list/">Next</a> 
									 </div> 
									</div>
<script type="text/javascript">
jQuery(document).ready(function($) {
 $.post('https://dineshonjava.com/wp-admin/admin-ajax.php', {action: 'mts_view_count', id: '4239'});
});
</script>
Strategy Design Patterns We can easily create a strategy design pattern using lambda. To implement…
Decorator Pattern A decorator pattern allows a user to add new functionality to an existing…
Delegating pattern In software engineering, the delegation pattern is an object-oriented design pattern that allows…
Technology has emerged a lot in the last decade, and now we have artificial intelligence;…
Managing a database is becoming increasingly complex now due to the vast amount of data…
Overview In this article, we will explore Spring Scheduler how we could use it by…