Finding the Middle Node of a Linked List

Finding the Middle Node of a Linked List
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
Linked List

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:

Input Linked ListOutput
1->2->3->4->5->NULL3
10->20->30->40->NULL30

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 Codestudio 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

blog banner 1
  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();
     }
}

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)

Approach 2 For Middle Node Linked List

Instead of traversing the Linked List twice, the middle node of a linked list can be found in a single traversal as well by using a two-pointer approach.

The idea is two use two pointers, slow and fast, respectively. Move the slow pointer by one step and the fast pointer by two steps. Proceeding this way, when the fast pointer will reach the end of the Linked List, the slow pointer will be at the middle of the Linked List.

Algorithm:

The approach is a slight variation of the Tortoise Hare Approach:

  1. Initially, both the pointers point to the first node of the Linked List. Move the slow pointer by one position and the fast pointer by two positions.
First_node_linked_list
First Node
  1. The slow pointer now points to the second node and the fast pointer points to the third node respectively.
second_node_linked_list
Second Node
  1. The slow pointer is now pointing to the third node and the fast pointer is now pointing to the fifth node.
Third_node_Linked_list
Third Node

Clearly, we see that if the fast pointer cannot make a move or fast.next.next == null, then the slow pointer is at the middle node.

The approach works for a Linked list with an odd number of nodes as well as shown below.

  1. Initially, both the pointers are pointing to the first node of the linked list. Move the slow pointer by one position and the fast pointer by two positions.
First_node_Linked_list
First Node
  1. Now the slow pointer is pointing to the second node and the fast pointer is pointing to the third node of the Linked list.
second_node_linked_list
Second node
  1. Now the slow pointer is pointing to the third node and the fast pointer is pointing to the last node as shown below.
Third_node_linked_list
Third_Node

It is clear from the above illustration that in the case of an even number of nodes in the linked list, the middle node will be reached once the fast pointer points to null, and in case of an odd number of nodes in the linked list, the middle node will be reached once the fast pointer points to the last node.

Code:

Below is the code to find the middle of the linked list using two pointer approach

// Two pointer approach to find the middle node of a linked list

public void findMiddleNode()
 {
        Node slowPtr = head;
        Node fastPtr = head;
        
        while(fastPtr.next != null && fastPtr.next.next != null)
        {
            fastPtr = fastPtr.next.next;
            slowPtr = slowPtr.next;
        }
        
        System.out.println("Middle node of a linked list is : " + slowPtr.key);
    }

Complexity Analysis:

The list is iterated once, so the time complexity of the above method is O(N), where N is the length of the Linked List

The space complexity is O(1) as no extra space is used.

Approach 3 For Linked List

If you are lucky enough that your interviewer allows you to use the Linked List class of collection framework, then finding the middle of the linked list becomes quite straightforward.

GIF_LINKED_LIST
GIF

Code:

import java.util.LinkedList;
public class Main{
    public static void main(String[]args)
    {
        LinkedList<Integer> ll = new LinkedList<>();
        ll.add(10);
        ll.add(20);
        ll.add(30);
        ll.addLast(40);
        ll.addLast(100);
        System.out.println("Given Linked list is : " + ll);
        int mid = ll.get(ll.size()/2);

        System.out.println("Middle node of a linked list is:  " + mid);
    }
}

The output of the above program is:

Given Linked list is: [10, 20, 30, 40, 100]
Middle node of a linked list is: 30

While most interviewers prefer to ask for direct implementation, some interviewers might also ask specifically for the above approach so as to test the knowledge of the Collection Framework in Java.

Frequently Asked Questions

How do you find the middle element of a linked list?

To find the middle element of a linked list, there are two possible approaches:
1. Iterate the list of elements once and count the number of nodes in the list. Once again iterate through the list this time only till the (count/2) position. The element at position (count/2) is the middle element.
2. Use two pointer approach as discussed above

What is the time complexity for finding the middle element of a linked list?

The time complexity of both the approaches as discussed above is O(N) where N is the size of the linked list.

Can Linked List contain duplicate elements?

Yes a Linked list can contain duplicate elements.

Key Takeaways

This article discussed various approaches to find the middle node of a linked list. With this done you can now practice more questions related to the Linked List approach on Codestudio.


If you are new to programming and want to learn more about programming languages, do check out the guided path available for free and amazing courses offered by Coding Ninjas.