How to Find middle element in a linked list - The Coding Shala

Home >> Interview Prep >> Find the middle element in a linked list

 In this post, we will learn how to find the middle element in a linked list and will implement its solution in Java.

Find a middle element in a linked list Problem

Given a singly linked list of N nodes. The task is to find the middle of the linked list.

Example 1:
Input:
LinkedList: 1->2->3->4->5
Output: 3 
Explanation: 
Middle of linked list is 3.

Example 2: 
Input:
LinkedList: 2->4->6->7->5->1
Output: 7 
Explanation: 
Middle of linked list is 7.

Find a middle element in a linked list Java Solution

Approach 1

You can find the total length of the linked list then traverse again from starting and return the middle element.

A better approach is to take two pointers one is a slow pointer, move by one step, and one fast pointer, move by two steps. At the time the fast pointer reaches the end slow is at the middle node.

Java Program: 

/* Node of a linked list
 class Node {
   int data;
    Node next;
    Node(int d)  { data = d;  next = null; }
}
*/

class Solution
{
    int getMiddle(Node head)
    {
         Node slow = head;
         Node fast = head;
         while (fast != null && fast.next != null) {
             slow = slow.next;
             fast = fast.next.next;
         }
        return slow.data;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Add two numbers in Scala - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Goal Parser Interpretation LeetCode Solution - The Coding Shala

Maximum Population Year LeetCode Solution - The Coding Shala

Shell Script to find sum, product and average of given numbers - The Coding Shala