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. After removing the second node from the end, the linked list becomesn= 21->2->3->5.

**Note:**

Given *n* will always be valid.

**Follow up:**

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ðŸ˜‡

#### Basic knowledge

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

**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:
head = 1->2->3->4->5->null
n = 2;
```

**Create a dummy newHead node**

```
ListNode newHead = new ListNode(0);
newHead = 0->null;
```

**Assign head, next to the newHead**

```
newHead.next = head;
newHead = 0>1->2->3->4->5->null;
```

**Assign newHead node to the fast and slow pointers**

```
ListNode fast = newHead;
fast = 0->1->2->3->4->5->null;
ListNode slow = newHead;
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.

**Already, slow pointer reference is with newHead.newHead = 0->1->2->3->5->null;**

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

## Solution

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode newHead = new ListNode(0); newHead.next = head; ListNode fast = newHead; ListNode slow = newHead; while(n > 0) { fast = fast.next; n--; } while(fast.next != null) { slow = slow.next; fast = fast.next; } slow.next = slow.next.next; return newHead.next; } }

**Time Complexity : O(n)**

**Space Complexity: O(1)**

**Note**: I love to teach programming in simple and fun way. I’m consistently making algorithms and data structures tutorials here. To get newsletter and notification of my new articles, please follow my blog via email. This is not spam, I’m a Full Stack Web Developer working in a Good product based company, Coimbatore.