## Task description:

Given the `head` of a linked list, remove the `nth` node from the end of the list and return its head. \n 

**Example 1:**

```java
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
```

**Example 2:**

```java
Input: head = [1], n = 1
Output: []
```

**Example 3:**

```java
Input: head = [1,2], n = 1
Output: [1]
```

**Constraints:**

* The number of nodes in the list is sz.
* 1 <= sz <= 30
* 0 <= Node.val <= 100
* 1 <= n <= sz


---

## Reasoning:

Let’s try to do something natural. To remove the **Nth** node from the end, it's essential to first determine the total number of nodes in the list. By counting the number of nodes, it becomes straightforward to identify the index of node that needs to be removed. There are two possible scenarios here. The first and simplest scenario is removing a non-edge node. In this case, all we need to do is change the pointer of the previous node (`next`) to the node after the one that was removed.

Let's look at an example: List → \[1,2,3,4,5\] , n=2.

\
 ![](https://cdn.hackernoon.com/images/rOSkQXtq7FclP5kp7uY7HWXRaLv1-1293pfz.png)

\
The second scenario is removing the first node, which is a special case as we don't have the previous node. The solution is straightforward, we just need to return the second node as the new head.

\
 ![](https://cdn.hackernoon.com/images/rOSkQXtq7FclP5kp7uY7HWXRaLv1-3za3pgp.png)

\
Let's evaluate the complexity of this approach. We perform two full traversals of the list, so the time complexity is O(2 \* N), and as we only store the size of the list, the space complexity is O(1).

### Code:

```java
public ListNode removeNthFromEnd(ListNode head, int n) {
        int size = 0;
        ListNode tmp = head;
        while (tmp != null) { 
            size++;
            tmp = tmp.next;
        }
        int prevIndex = size - n;
        if (prevIndex == 0) return head.next;
        
        tmp = head;
        while (prevIndex != 1) {
            tmp = tmp.next;
            prevIndex--;
        }
        tmp.next = tmp.next.next;
        return head;
    }
```

\
## How to optimize this solution?

By closely examining the conditions, we can see that the number of node to be removed is specified by a value such that `1 <= n <= sz`, where **sz** is the size of the list. The solution involves using two pointers. We create a fast pointer that points to the **Nth** node and a slow pointer that points to the head of the list.

\
 ![](https://cdn.hackernoon.com/images/rOSkQXtq7FclP5kp7uY7HWXRaLv1-olb3pqp.png)

\
Next, we iterate until the fast pointer reaches the end of the list. The slow pointer lags behind the fast pointer by n, so it now points to the node preceding the one we want to delete.

\
 ![](https://cdn.hackernoon.com/images/rOSkQXtq7FclP5kp7uY7HWXRaLv1-cmd3pe7.png)

\
And then, we follow the same steps as before and change the pointer of the previous node to the node after the one that was removed.

### Code:

```java
public ListNode removeNthFromEnd(ListNode head, int n) {
  int delay = n;
  ListNode fast = head;
  while(delay > 0) {
    delay--;
    fast = fast.next;
  }
  if (fast == null) return head.next; // point
      
  ListNode prev = head;
  while (tmp.next != null) {
    tmp = tmp.next;
    prev = prev.next;
  }

  prev.next = prev.next.next;
  return head;
}
```

\
I'd like to emphasize a few important points in this code. We must remember the scenario where the first node must be removed. In this scenario, the fast pointer will be null, and we should return the second node as the new head of the list. As we can see, we have successfully found and removed the node in just one pass through the list.

**Complexity:**


1. Time complexity: `O(N)`
2. Space complexity:  `O(1)`

   \

 ![](https://cdn.hackernoon.com/images/rOSkQXtq7FclP5kp7uY7HWXRaLv1-c9f3p47.png)

\
I hope this article was helpful in clarifying how to tackle this kind of problem. I would appreciate your feedback.

See you soon! ✌

The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.

Read My Stories

Too Long; Didn't Read

Cassandra Forward a free Cassandra-focused community event

How to Remove Nth Node From End of List — Blind 75 LeetCode Question

Too Long; Didn't Read

@top4ikru

Credibility

RELATED STORIES