# 19. Remove Nth Node From End of List

### Leetcode

<https://leetcode.com/problems/remove-nth-node-from-end-of-list/>

### 題目

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

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/10/03/remove_ex1.jpg)

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

**Example 2:**

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

**Example 3:**

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

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

hashmap

```
var removeNthFromEnd = function(head, n) {
    // 只有一個元素的狀況，刪掉一個等於 null
    if(!head.next) return null;
    
    const map = new Map();
    
    let i = 1;
    let pointer = head;
    while(head) {
        map.set(i, head);
        i++;
        head = head.next;
    }
    const lastNode = map.get(i-n-1);
    if (lastNode) {
        lastNode.next = lastNode.next.next;
        return pointer;
    } else {
        // lastNode 不存在，代表要刪掉的是第一個元素
        return pointer.next;
    }
};
```

Runtime: 139 ms, faster than 6.81% of JavaScript online submissions for Remove Nth Node From End of List.

Memory Usage: 39.4 MB, less than 98.63% of JavaScript online submissions for Remove Nth Node From End of List.

* **方法二**

Two pass algorithm

```
var removeNthFromEnd = function(head, n) {
    if(!head.next) return null;
    
    let i = 0;
    let pointer = head;
    while(head) {
        i++;
        head = head.next;
    }
    i = i - n - 1;
    head = pointer;
    
    // 代表要刪掉的是第一個元素
    if(i<0) return pointer.next;
    while(i) {
        head = head.next;
        i--;
    }
    head.next = head.next.next;
    
    return pointer;
};
```

Runtime: 80 ms, faster than 67.89% of JavaScript online submissions for Remove Nth Node From End of List.

Memory Usage: 40.1 MB, less than 72.75% of JavaScript online submissions for Remove Nth Node From End of List.

* **方法三**

One pass algorithm

firstNode 先往前走，等到 firstNode 走到 n 的位置，secondNode 再跟 firstNode 一起走，等到 firstNode 走到底時，secondNode 即是我們要找的位置

```
var removeNthFromEnd = function(head, n) {
    let first = head;
    let second = head;
    
    let i = 0;
    while(first) {
        // 當 firstNode 走到超過 n 時，secondNode 再一起往前走
        if(i > n) {
            second = second.next;
        }
        first = first.next;
        i++
    }
    // 代表要刪掉的是第一個元素
    if(i===n) return head.next;
    second.next = second.next.next;
    
    return head;
};
```

Runtime: 97 ms, faster than 30.13% of JavaScript online submissions for Remove Nth Node From End of List.

Memory Usage: 39.8 MB, less than 86.38% of JavaScript online submissions for Remove Nth Node From End of List.
