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 th