How to find middle of a linked list in one iteration ? - Leetcode Solution

Companies:

Apple

LeetCode: How to find middle of a linked list in one iteration ? Leetcode Solution

Difficulty: Unknown

How to find middle of a linked list in one iteration ?

There are multiple ways to find middle of a linked list. In this article, we discuss the two approaches to find the middle element of the linked list.

You can also see the below video, if you want to understand the approaches using a video solution.

Approach 1

In this approach, we will find n which is the size of the linked list. Once we find n, we know the middle element will be located at position n/2. This approach requires two iterations :

First iteration for finding the value of n.
Second iteration for travelling to the middle of the linked list.

This approach’s time complexity is O(n) but the number of iterations is still 2.

Approach 2 (Single Iteration)

This approach uses two pointer method in which we create two pointers. One fast pointer and one slow pointer.
In every iteration, the slow pointer moves one step at a time and the fast pointer moves two steps at a time. Once the fast pointer reaches the end, the slow pointer would be at the middle of the linked list.

Proof

Since, the slow pointer moves one step at a time and the fast pointer moves two steps at a time, after x iterations, the slow pointer would have moved to x position and the fast pointer would have moved to 2x position.
Therefore, when the fast pointer reaches the end 2x becomes equal to n.
=> 2x = n
=> x = n/2
Therefore, when the fast pointer reaches the end , the slow pointer is at position x which is n/2, which is the middle of the linked list.

Algorithm

Step 1: Initialize two pointers one fast_pointer, and one slow_pointer to the start of the linked list.
Step 2: While fast_pointer does not reach the end do the following :
Step 3: Move slow_pointer by one step and fast_pointer by two steps

See the flowchart below for the steps:

Similar Problems