Kth Node from Middle

Problem Statement

Given an integer B and a linked list A of length N.

From the middle of the Linked List towards the beginning, we have to determine the value of the Bth node.

Return -1 if such an element is not present.

Note:

The position of the middle node is:

(N / 2) + 1

Example 1

Input:

A: 1 -> 2 -> 3 -> 4 -> 5
B: 2

Output:

1

Explanation:

Middle node is:

3

Now move:

2

nodes towards the beginning.

3 -> 2 -> 1

Answer:

1

Example 2

Input:

A: 1 -> 2 -> 3 -> 4 -> 5
B: 0

Output:

3

Explanation:

If:

B = 0

then we need the middle node itself.

So answer is:

3

Today I solved this Linked List question.

Since I solved the previous question which was finding the middle node using Slow and Fast Pointers, the first instinct that came into my mind was to somehow use the same pattern here as well.

My First Thought

My first thought was actually a little different from the final solution.

Since we need the Bth node from the middle, I was thinking:

What if I make the fast pointer move ahead by B nodes?

Then if the fast pointer reaches the middle node, maybe the slow pointer would automatically reach the Bth node from the beginning of the middle.

Something like:

slow = head;
fast = head;

and then maintaining some distance between them.

Honestly, I was struggling to visualize whether this would actually work or not 😭.

The idea sounded correct in my head, but I wasn't fully convinced.

And even if it worked, I wasn't sure how I would write the code for it.

So instead of forcing that approach, I started thinking from another direction.

My Actual Thought Process

As mentioned in the question:

We need to find the Bth node from the middle towards the beginning.

That means:

Start from middle
Move B nodes backwards

Now Linked Lists cannot move backwards.

So instead of thinking about nodes, I started thinking about positions.

If I somehow know the position of the middle node, then I can directly calculate the position of the answer.

Something like:

targetNode = middleNode - B;

And suddenly the problem looked much easier.

Let's take:

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

Middle position:

3

and:

B = 2

So:

targetNode = 3 - 2
           = 1

Now I simply need to reach position:

1

and return its value.

Answer becomes:

1

Finding The Middle Position

For finding the middle node, I used the same Slow and Fast Pointer technique that I learned in the previous question.

We take:

slow
fast

Initially:

slow = head
fast = head

The slow pointer moves:

1 step

The fast pointer moves:

2 steps

And by the time fast reaches the end of the Linked List, slow reaches the middle.

At the same time, I also keep track of the middle position using:

middleNode

which starts from:

1

and increases whenever slow moves.

Let's take:

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

Initially:

slow = 1
fast = 1
middleNode = 1

First iteration:

slow = 2
fast = 3
middleNode = 2

Second iteration:

slow = 3
fast = 5
middleNode = 3

Now:

fast.next == null

So the loop stops.

Middle position becomes:

3

Finding The Target Position

Now:

middleNode = 3
B = 2

So:

targetNode = middleNode - B
           = 1

Now I simply start from the head and traverse till:

targetNode

position.

In this case:

Position 1 = Node 1

So the answer becomes:

1

Edge Case

Suppose:

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

and:

B = 5

Middle position:

3

Now:

targetNode = 3 - 5
           = -2

This position does not exist.

So according to the question, we return:

-1

That's why I added:

if(targetNode <= 0){
    return -1;
}

This Was My Code

public class Solution {
    public int kthNode(ListNode head, int B) {

        ListNode slow = head;
        ListNode fast = head;

        int middleNode = 1;

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

        int targetNode = middleNode - B;

        if(targetNode <= 0){
            return -1;
        }

        ListNode temp = head;

        for(int i = 0; i < targetNode - 1; i++){
            temp = temp.next;
        }

        return temp.val;
    }
}

The thing I liked about this question was that it directly connected with the previous Middle Node question (and also proud of myself hehe)

A few minutes before solving this, I was still thinking about Slow and Fast Pointers and trying to somehow use them again here.

Even though I didn't end up using my initial idea, it still helped me think in the right direction because the first step of the solution was again finding the middle node.

Another Linked List question added .

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