# 13) Remove Nth Node From End of List

Hi friends, in this article we going to see how to remove the Nth node from end of the list. Here is our given problem,

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

```Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
```

Note:

Given n will always be valid.

Could you do this in one pass?

Before moving into the solution, I ask, you guys try to come up with your own approach. Take 5 to 10 minutes time, try to solve the problem.

If you really has done, I appreciate your work, you are greatðŸ˜‡

#### How can we APPROACH this problem?

In our given question, they mentioned Could you do this in one pass? That is we have to solve this problem with O(n) time complexity.

### BEst way

1. Slow and Fast Pointer Approach

#### Do you know?

If you know Slow and Fast Pointer approach, you can able to solve most of the Linked List Problems easily.

See my previous articles, I have solved most of the linked list problems in O(n) time complexity with Slow and Fast pointer approach.

### Steps to Solve

``````Input:

n = 2;
``````

``````ListNode newHead = new ListNode(0);

``````newHead.next = head;

Assign newHead node to the fast and slow pointers

``````ListNode fast = newHead;
fast = 0->1->2->3->4->5->null;

slow = 0->1->2->3->4->5->null;``````

Now move fast pointer 0 to n positions, so that the gap between slow and fast becomes n

``````while(n > 0)
{
fast = fast.next;
n--;
}``````

In our case, n = 2

``````Iteration first time, n = 2

fast = fast.next;
fast = 1->2->3->4->5->null;

n--;
n = 1;

Iteration second time, n = 1

fast = fast.next;
fast = 2->3->4->5->null;

n--;
n = 0;

Iteration third time, n = 0
Since n is equal to 0, it breaks and comes out of the while loop. ``````

Still now we have,

``````fast = 2->3->4->5->null;
slow = 0->1->2->3->4->5->null;``````

We maintained a gap between fast and slow is n.

Now, move fast and slow pointer simultaneously, still fast.next becomes null;

It indicates that, when fast.next becomes null, slow pointer is standing infront of the nth node.

Therefore, slow.next = slow.next.next;
By assigning slow’s next’s next pointer to slow’s next, removes the nth node.

``````while(fast.next != null)
{
fast = fast.next;
slow = slow.next;
}``````
``````In our case,
fast = 2->3->4->5->null;
slow = 0->1->2->3->4->5->null;``````
``````
Iteration first time, fast.next != null
fast = fast.next;
fast = 3->4->5->null;

slow = slow.next;
slow = 1->2->3->4->5->null;

Iteration second time, fast.next != null
fast = fast.next;
fast = 4->5->null;

slow = slow.next;
slow = 2->3->4->5->null;

Iteration third time, fast.next != null
fast = fast.next;
fast = 5->null;

slow = slow.next;
slow = 3->4->5->null;

Iteration fourth time, fast.next == null.
Breaks the condition, comes out of the while loop. ``````

Still now we have,

``````fast = 5->null;
slow = 3->4->5->null;``````
``````slow.next = slow.next.next;
By assigning slow's next's next pointer to slow's next, removes the nth node.

slow = 3->5->null;``````

Hence, we remove the nth node.

When I return, newHead.next, I will get my desired list

## Solution

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {

while(n > 0)
{
fast = fast.next;
n--;
}

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

slow.next = slow.next.next;