Find the Middle of a Linked List

In this article, we will tackle a common problem asked in the linked list which is finding the middle node of a singly linked list. This problem is frequently asked in coding interviews and has a simple solution.

Example:

1 -> 2 -> 3 -> 4 -> 5 -> NULL

Output:

Middle Node: 3

If the linked list has an even number of nodes:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

Output:

Middle Node: 3 or 4

So we are given the head of a singly linked list, and we need to return the middle node of the linked list. If there are two middle nodes, return the second middle node.

Solution:

For this problem, we can use the two-pointer technique, also known as the "slow and fast pointer" approach.

Steps to Solve:

Make Two Pointers:

We create two pointers, slow and fast, both initially pointing to the head of the list.

Move the Pointers:

Move the slow pointer one step at a time.

Move the fast pointer two steps at a time.

Find the Middle Node:

When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.

Time Complexity: O(N)

Space Complexity: O(1)