Solution: Middle of the Linked List

Statement

Given the head of a singly linked list, return the middle node of the linked list. If the number of nodes in the linked list is even, there will be two middle nodes, so return the second one.

Constraints:

Let n be the number of nodes in a linked list.

• $1 \leq$ n $\leq 100$
• $1 \leq$ node.data $\leq 100$
• head $\neq$ NULL

Solution

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

In the naive approach, we use an external array to store the elements of the linked list, and then we return the element present at the index $\lfloor \frac{array.length}{2} \rfloor$ as the middle node of the linked list. The time and space complexity of this approach is $O(n)$, where $n$ is the number of nodes in the linked list. Let’s see if we can solve this problem with better time and space complexity.

Optimized approach using fast and slow pointers