Introduction

Given a singly linked list, find middle of the linked list. For example, if given linked list is 1->2->3->4->5 then output should be 3.

If there are even nodes, then there would be two middle nodes, we need to print second middle element. For example, if given linked list is 1->2->3->4->5->6 then output should be 4.

Approach

We use the tortoise and hare approach where we have a fast and a slow pointer. When the fast pointer reaches the end, the middle pointer reaches the middle position.

Code

/* Node of a linked list
 class Node {
   int data;
    Node next;
    Node(int d)  { data = d;  next = null; }
}
*/
class Solution
{
    int getMiddle(Node head)
    {
         // Your code here.
         var slow = head;
         var fast = head;
         while (fast != null && fast.next != null) {
             slow = slow.next;
             fast = fast.next.next;
         }
         return slow.data;
    }
}
Java Program using slow and fast pointers

References

Finding middle element in a linked list | Practice | GeeksforGeeks
Given a singly linked list of N nodes. The task is to find the middle of the linked list. For example, if given linked list is 1->2->3->4->5 then the output should be 3.If there are even nodes, then there would be two middle nodes,
Find the middle of a given linked list in C and Java - GeeksforGeeks
A computer science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.