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



Thanks for feedback.



Read More....
Clone a Linked List
Check if linked list nodes form a palindrome
Delete a node at specific position from linked list
Delete a node from linked list
Detect if cycle is present in a linked list