LC 2095. Delete Middle Node of Linked List (Medium

🔗: Delete the Middle Node of a Linked List - LeetCode

Problem Statement

You are given the head of a linked list.

Delete the middle node and return the head of the modified linked list.

The middle node of a linked list of size n is:

⌊n / 2⌋

using 0 based indexing.

Example 1

Input:

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

Output:

1 -> 2 -> 4 -> 5

Explanation:

Middle node is:

3

so after deleting it:

1 -> 2 -> 4 -> 5

Example 2

Input:

2 -> 4 -> 8 -> 6

Output:

2 -> 4 -> 6

Explanation:

Middle node is:

8

so after deleting it:

2 -> 4 -> 6

This is one of another Linked List question I solved.

When I read the question, the first thing that came into my mind was:

Find the middle node first.

Because I had literally solved the Middle of Linked List type questions before this one

So naturally my brain went towards the same Slow and Fast Pointer pattern.

My First Thought (Brute Force)

My first thought was pretty straightforward.

If I can find the length of the Linked List, then I can calculate the middle position.

For example:

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

Length:

5

Middle position:

5 / 2 = 2

using 0-based indexing.

Now I can traverse till the middle node and delete it.

At first this approach felt correct.

But then I realized something.

To delete a node in a singly Linked List, I cannot stand on the node itself.

I need to stand on the node before it.

For example:

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

If I want to delete:

3

I need:

2

because deletion happens like:

2.next = 4

and now:

3

gets removed from the Linked List.

The Question That Confused Me

After that I started thinking about the optimized solution.

I already knew how to find the middle node using:

slow
fast

But then I got stuck on one thing.

If:

slow

reaches the middle node,

how do I know which node was standing before it?

Because Linked Lists cannot move backwards.

I remember asking myself:

Do I need another pointer to keep track of the node before the middle?

And the answer was (Drum rollsss) : YESSS

Optimized Approach

We use:

prev
slow
fast

Initially:

prev = null
slow = head
fast = head

The slow pointer moves:

1 step

The fast pointer moves:

2 steps

And before moving slow, we store:

prev = slow

so that prev always remains one node behind slow.

Let's dry run.

Example:

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

Initially:

prev = null
slow = 1
fast = 1

First Iteration

prev = 1
slow = 2
fast = 3

Second Iteration

prev = 2
slow = 3
fast = 5

Now:

fast.next == null

So the loop stops.

Current state:

prev = 2
slow = 3

Notice something?

slow

is exactly at the middle node.

And:

prev

is exactly one node before it.

Which is exactly what we need for deletion.

Now deletion becomes:

prev.next = slow.next;

which means:

2.next = 4;

Result:

1 -> 2 -> 4 -> 5

Done yayy😭.

Edge Case

What if there is only one node?

Example:

1

The middle node is:

1

itself.

After deleting it:

null

should be returned.

This is why we need a separate check for:

head.next == null

This Was My Code

public ListNode deleteMiddle(ListNode head) {

    if(head == null || head.next == null){
        return null;
    }

    ListNode prev = null;
    ListNode slow = head;
    ListNode fast = head;

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

    prev.next = slow.next;

    return head;
}

The thing I liked about this question was that it felt like a direct extension of the Middle of Linked List problem.

The middle node pattern stayed exactly the same.

The only new thing I learned was that sometimes finding the answer is not enough.

You also need to keep track of the node before the answer.

And that is where the extra:

prev

pointer came into the picture.

It's honestly pretty satisfying to see how these patterns build on top of each other. First I learned how to find the middle node, then how to find the Kth node from the middle, and now how to delete the middle node itself.

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!!