Find middle element of linked list with odd no of nodes

Write a program to find the middle node of the linked list where the linked list is having odd no of nodes

To find the middle node of linked lists we find the length of the linked list
Once we know the length, we find the middle and traverse till that position and get the middle node

Algorithm

1. Firstly find the length of the linked list
2. Set variable middlePos as (length/2)+1 for getting the middle position of the linked list which has an odd number of nodes
3. Traverse till that position using a loop
4. Print the data of the middle node

Complexity

Time Complexity : O(n) , where n is the number of nodes in the linked list
Space Complexity : O(1)

Java Code

import java.util.*;

class FindMiddle{
        
        class Node {
            // initialising data field and next pointer of node
            int data;
            Node next;
         
            Node(int d) {
                this.data = d;
                this.next = null;
            }
        }
     
        Node head;
     
        // creating a linked list using array
        public void buildLinkedlist(int A[], int noOfNodes) {
            int i;
            Node temp, last;
            temp = new Node(A[0]);
            temp.next = null;
            head = temp;
            last = temp;
            for (i = 1; i < noOfNodes; i++) {
                temp = new Node(A[i]);
                temp.next = null;
                last.next = temp;
                last = temp;
            }
        }
     
        // printing of linkedList
        public void printLinkedlist() {
            List allNodesList = new ArrayList<>();
            Node temp = head;
            while (temp != null) {
                allNodesList.add(Integer.toString(temp.data));
                temp = temp.next;
            }
            System.out.println(String.join(" -> ", allNodesList));
        }
    
        //function to calculate length of linked list
        public int getLength() {
            Node temp = head;
            int count = 1;
            while (temp.next != null) {
                temp = temp.next;
                count++;
            }
            return count;
        }
    
        // function to get middle node of linked list
        public void getMiddleNode() {
            int middlePos = (getLength() / 2) + 1;
            Node current = head;
            for (int i = 1; i < middlePos; i++) {
                current = current.next;
            }
            System.out.println(current.data);
        }
     
        public static void main(String[] args) {
            int[] linkedlistElements = new int[] { 1,2,3,4,5};
            int numberOfNodes = linkedlistElements.length;
            
            FindMiddle ll = new FindMiddle();
            ll.buildLinkedlist(linkedlistElements, numberOfNodes);
            
            System.out.println("Given Linked List ");
            ll.printLinkedlist();
            
            System.out.print("Middle node of given Linked List is ");
            ll.getMiddleNode();
        }
 }

Output

Given Linked List
1 -> 2 -> 3 -> 4 -> 5
Middle node of given Linked List is 3