Finding The Middle Element - Singly Linked List

In our previous article we learnt what a singly linked list is and how to implement it in various languages. In this article we will see how to find the middle element or middle node in a singly linked list.

Note: Same approach can be used to find the middle element in a doubly linked list as well.

Problem Statement

Given a singly linked list, find the middle element in it. If there are even number of nodes in the given linked list then return the ceil value node as the middle element. E.g. if there are 6 nodes in the given linked list, then node 4 should be considered as the middle node.

Examples

Example 1:

Input: 1 -> 2 -> 3 -> 4 -> 5 
Output: 3

Example 2:

Input: 2 -> 4 -> 6 -> 8 -> 10 -> 12 
Output: 8

Solution 1: Counting Nodes

This method works on the idea of counting the total no. of nodes in the given linked list and using this information to find out which is the middle element.

This algorithm involves the following steps:

1. Traverse all the nodes in the given linked list starting from the head node.

2. Take a variable to keep track of the count of total nodes traversed. Lets call this variable nodeCount.

3. Once you have the count of total nodes in a linked list, you can get the middle node using middleNode = nodeCount/2.

4. Now traverse the linked list again from the head node until middleNode. To do this take a variable currentNodeCount to keep track of the current node count. As you visit each node, increment this counter by 1. When currentNodeCount is equal to middleNode we have reached the middle node, return the middle node.

Implementation

Note: For linked list, node class/struct definitions please refer our singly linked list article.

Language: Go

Language: Java

Complexity Analysis

Time Complexity: O(n)

Since we make 2 passes (one full pass and one pass till the middle node) on the given linked list, time complexity is O(n) + O(n/2) which in general can be represented as O(n).

Space Complexity: O(1)

No extra space is used.

Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Educative IO Tutorials

Solution 2: Two Pointer Technique

As you might have noticed in solution 1, we have to traverse the given linked list twice in order to find the middle node, first to count the total number of nodes and then till the middle element to return the result.

This problem can be solved more efficiently using the two pointer technique. In this method we have to traverse the list just once to arrive at the result.

This approach works on the idea that, when we move the two pointers, one pointer twice as fast as the other, by the time the fast pointer reaches the end of the list, the slow pointer would have moved till the middle of the list.

This algorithm involves the following steps:

1. Take two pointers variables, lets call them fast and slow.

2. Initially both fast and slow points to the head node of the given linked list.

3. slow pointer moves one step at a time and fast pointer moves two steps at a time.

4. We need to move the fast and slow pointers from the head node until the fast pointer reaches end of the list.

5. When the fast pointer reaches the last node, slow pointer would have reached the middle node since it is moving at half the pace as the fast pointer.

6. So when the fast pointer reaches the last node, return the slow pointer node as your result.

Lets understand this with an example. Consider you are given the below linked list:

We point the slow and fast pointers initially to the head node as shown in figure below:

Now, in each iteration we move the slow pointer one step at a time and fast pointer two steps at a time until fast pointer reaches the last node. Same is shown in the below diagrams.

Iteration 1

Iteration 2

Once the fast pointer reaches the last node (node 5 in this case) we return the slow pointer which is currently pointing to the middle node (node 3 in this case) as the result.

Implementation

Language: Go

Language: Java

Complexity Analysis

Time Complexity: O(n)

Time complexity is O(n) since we need to make one pass on the given linked list.

Space Complexity: O(1)

No extra space is used.

Now you know how to find middle element in a singly linked list. Do not stop here, deepen your knowledge by exploring more articles on linked lists.

That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you.

If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form).

You can explore more such amazing articles from code recipe here.

Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time: Join now

Follow us on social media: Facebook, Twitter, Linkedin, Tumblr, Instagram.