Leetcode: Middle of the Linked List (Kotlin)

Introduction

Middle of the Linked List is an easy Linked List problem. I like this problem because it provides a gentle introduction to the fast and slow pointer pattern for Linked Lists. This is a common pattern used in more complex Linked List problems.

I will show the approach to solving this in this article. Middle of the Linked List - LeetCode

Problem Statement

Examples

Constraints

First Approach

My first thought was to go through the list to count how many nodes it has. Then I would divide the number of nodes by two to get where the middle position. I would finally go through the list again and count up again until I reach the middle position. {% gist https://gist.github.com/cmcoffeedev/af2b44f75a51b29f8f6fca6379d151b0.js %}

Fast and Slow Pointer Approach

After doing more research, I was introduced to the fast and slow pointer pattern for linked lists. You will see this mentioned more with the Linked List Cycle Question and Floyd’s Cycle Detection algorithm.

Have a fast and slow pointer that starts at the head node.
We will then traverse both nodes at the same time but at different speeds. The slow pointer will move up once each time, and the fast pointer will move up two nodes each time. Since the fast node moves up twice, we need to check if it’s null and if its next node is null.
The fast pointer will eventually hit the end of the list, which will break us out of the loop.
Return the slow pointer since it should now be at the middle node.

Fast and Slow Pointer Solution

{% gist https://gist.github.com/cmcoffeedev/b4ce8589273ff30f170b6710adaf49aa.js %}>