# Finding The Middle Element - Singly Linked List

Updated: Jun 3, 2022

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:

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

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

**nodeCount**.Once you have the count of total nodes in a linked list, you can get the middle node using

**middleNode**=**nodeCount**/2.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:**

## 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:

Take two pointers variables, lets call them

**fast**and**slow**.Initially both

**fast**and**slow**points to the head node of the given linked list.**slow**pointer moves one step at a time and**fast**pointer moves two steps at a time.We need to move the

**fast**and**slow**pointers from the head node until the**fast**pointer reaches end of the list.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.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.