LC 876 . Middle of the Linked List (Easy)

🔗: https://leetcode.com/problems/middle-of-the-linked-list/

Problem Statement

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1

Input:

head = [1,2,3,4,5]

Output:

3

Example 2

Input:

head = [1,2,3,4,5,6]

Output:

4

Explanation:

There are two middle nodes:

3 and 4

The question asks us to return the second middle node.

So we return:

4 

Today I solved this Linked List question.

I actually started Linked Lists a while ago before my vacations, but because of exams I left them in between.

So today I picked up an easy Linked List problem to get back into them.

My First Thought (Brute Force)

The first thing that came into my mind was that Linked Lists are not like arrays.

In arrays, we already know the size.

But Linked Lists are dynamic.

So before finding the middle node, I first need to know the length of the Linked List.

To find the length, I made a temporary pointer:

temp = head

and traversed the Linked List until:

temp == null

while counting the nodes.

Let's take:

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

After traversing the entire Linked List:

len = 6

Now I know the length.

So I again make:

temp = head

and move it:

len / 2

times.

For this example:

6 / 2 = 3

So I move:

1 -> 2 -> 3 -> 4

and stop at:

4

which is exactly the second middle node needed.

This was my brute force approach.

Brute Force Code

int len = 0;
SLLNode<Integer> temp = head;

while(temp != null){
    len++;
    temp = temp.next;
}

temp = head;

for(int i = 0; i < len / 2; i++){
    temp = temp.next;
}

return temp;

Optimized Approach

After solving it this way, I watched a video to understand if there was a better approach.

And that is where I came across a very common Linked List pattern:

Slow Pointer + Fast Pointer

I have seen two pointers in arrays before, but this was my first time learning this pattern in Linked Lists.

Understanding Slow and Fast Pointer

The idea is actually very simple.

We take two pointers:

slow = head
fast = head

The slow pointer moves:

1 step at a time

The fast pointer moves:

2 steps at a time

Now because the fast pointer is moving twice as fast, it will cover the entire Linked List much quicker.

And by the time the fast pointer reaches the end of the Linked List, the slow pointer will have covered only half the distance.

And half the distance means:

Middle Node

which is exactly what we need.

Example 1

Let's take:

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

Initially:

slow = 1
fast = 1

First Move

slow = 2
fast = 3

Second Move

slow = 3
fast = 5

Now:

fast.next == null

So the loop stops.

And where is slow?

3

which is exactly the middle node.

So we return it :

3

Example 2

Now let's take:

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

Initially:

slow = 1
fast = 1

First Move

slow = 2
fast = 3

Second Move

slow = 3
fast = 5

Third Move

slow = 4
fast = null

Now the fast pointer has completed traversing the Linked List.

And where is slow?

4

which is exactly the second middle node.

This is also what the question wants us to return.

The thing I liked about this approach is that I don't need to find the length at all.

I don't need two traversals.

I don't need to calculate:

len / 2

The pointers automatically take me to the middle node.

Why The Loop Condition?

while(fast != null && fast.next != null)

We check both conditions because the fast pointer is jumping:

2 nodes at a time

and we don't want a Null Pointer Exception.

If either:

fast == null

or

fast.next == null

the traversal stops.

Time Complexity

Brute Force:

O(n)

because we traverse the Linked List twice.

Optimized:

O(n)

because we traverse the Linked List only once.

Space Complexity

Brute Force:

O(1)

Optimized:

O(1)

This Is The Code That I Wrote

static SLLNode middleNode(SLLNode<Integer> head){

    SLLNode slow = head;
    SLLNode fast = head;

    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

My biggest learning from this question was getting introduced to the Slow and Fast Pointer technique.

The brute force solution was pretty straightforward because I already knew I could find the length and then reach the middle.

But the optimized solution was much cleaner and also introduced me to a very common Linked List pattern that I know is going to be used in many more questions.

Will continue solving more Linked List questions and documenting my thought process as I learn.

Any suggestions, corrections, or feedback would be appreciated.

Thanks for reading!!