Finding the Middle Node of a Linked List

Introduction

A linked List is a linear data structure that consists of nodes. Each Node contains a data field and a pointer to the next Node. In Linked List, unlike arrays, elements are not stored at contiguous memory locations but rather at different memory locations. The various elements in a linked list are linked together using pointers.

Linked List is one of the important topics from an interview perspective. Almost all the major companies ask questions related to Linked List in the initial stages. One of the most frequently asked questions by Top Product based companies, including Amazon, Flipkart, Adobe, is “Find the Middle Node of a Linked List.”

The problem statement says, “Given a Linked List and a head pointer pointing to the first node of a linked list, find the middle node of a Linked list”

Example for Linked List:

Note that in the case of an even number of nodes in the Linked List, there will be two middle nodes. In that case, we need to print the first middle element. The various approaches to solve this problem are discussed in detail along with code in Java.

Recommended: Please solve it on Coding Ninjas Studio before moving on to the solution.

Approach 1 For Middle Node of a Linked List

The middle node of a Linked List is the element at (Number of Nodes/2)th position. We need to find the element at this position.

The problem thus reduces to the following two steps:-

• Find the number of elements(count) in the Linked List
• Print the element at (count/2)th position
   

Algorithm:

Step 1) An obvious approach would be to iterate through the Linked List and maintain a count variable that will keep the count of the number of nodes in the Linked List.

In the code below, the getCount() method is used for this.

Step 2) Now again iterate through the List till count/2 and return the Node at count/2.

In the code below, findMiddleNode() method is used for this.

Code:

For the sake of simplicity, the below program uses only two methods for insertion of a new node in the Linked List

1. push() -> To insert a node at the beginning of Linked List.
2. insertAtLast() -> To insert a node at the end of the Linked List.
    

public class MiddleNode
{
    Node head;
    // Node class
    class Node{
        int key;
        Node next;
        
        Node(int data)
        {
            key = data;
            next = null;
        }
    }
    
    // Method for inserting node to the front
    public void push(int data)
    {
        Node new_node = new Node(data);
        new_node.next = head;
        head = new_node;
    }
    
    // Method for inserting a node at the last
    public void insertAtLast(int data)
    {
        Node new_node = new Node(data);
        if(head == null){
            head = new_node;
            return;
        }
        
        
        Node temp = head;
        while(temp.next != null)
        {
            temp = temp.next;
        }
        
        temp.next = new_node;
        return;
    }
    
    

    // Method to get the count of number of nodes in the List
    public int getCount()
    {
        int count = 0;
        Node temp = head;
        while(temp!= null)
        {
            count++;
            temp = temp.next;
        }
        return count;
    }
    
    // Method to find the middle node of a linked list
    public void findMiddleNode()
    {
        int count = getCount();
        Node temp = head;
        
        // If the number of nodes are even, then there are
        // two middle nodes print the first middle node
        if(count%2 == 0)
        {
            int i = (count/2) - 1;
            while(i != 0)
            {
                temp = temp.next;
                i--;
            }
            
            System.out.println(temp.key);
        }
        
        // If the number of nodes are even
        else{
            int i = (count/2);
            while(i != 0)
            {
                temp = temp.next;
                i--;
            }
            System.out.println(temp.key);
        }
    }
    


   // A utility method to print the Linked List
    public void printList()
    {
        Node temp = head;
        while(temp != null)
        {
            System.out.print(temp.key + " ");
            temp = temp.next;

        }
    }
    public static void main(String []args)
    {
        MiddleNode ll = new MiddleNode();
        // Making a linked list of odd number of nodes
        // 1->2->3->4->5->NULL
        ll.push(1);
        ll.insertAtLast(2);
        ll.insertAtLast(3);
        ll.insertAtLast(4);
        ll.insertAtLast(5);
        System.out.println("Printing the original Linked List");
        ll.printList();
        System.out.println("\nThe middle node of a Linked list is");
        ll.findMiddleNode();


       // Making a linked list of even number of nodes
       // 10->20->30->40->50->60->NULL
        ll = new MiddleNode();
        ll.push(10);
        ll.insertAtLast(20);
        ll.insertAtLast(30);
        ll.insertAtLast(40);
        ll.insertAtLast(50);
        ll.insertAtLast(60);
         System.out.println("Printing the original Linked List");
        ll.printList();
        System.out.println("\nThe middle node of a Linked list is");
        ll.findMiddleNode();
     }
}

You can also try this code with Online Java Compiler

Run Code

The output of the above program is:

Printing the original Linked List
1 2 3 4 5
The middle node of a Linked List is
3
Printing the original Linked List
10 20 30 40 50 60
The middle node of a Linked List is
30

Complexity Analysis:

The Linked list is traversed two times. Once for the entire Linked List and second till the middle of Linked List. So the time complexity will be O(N) + O(N/2), which is equivalent to O(N), where N is the number of elements in the Linked List.

As no extra space is required, so the space complexity is O(1)

Recommended Topic, Floyds Algorithm And Rabin Karp Algorithm