# LeetCode Solution, Medium, 19. Remove Nth Node From End of List

# [19. Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)

## 題目敘述

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

**Example:**

![remove_ex1.jpeg](https://cdn.hashnode.com/res/hashnode/image/upload/v1655872702040/s2w1a7YkI.jpeg align="left")

    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]

**Constraints:**

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

**Follow up:** Could you do this in one pass?

**Hint 1:**

Maintain two pointers and update one with a delay of n steps.

### 題目翻譯

給定一個連結序列 `head`，從中刪除由結尾算起來第 `n` 個節點，並回傳 `head`。

## 解法解析

這個題目主要用兩種解法，第一種是 Two pointer 和第二種 One Pass。但不管這兩種其實重點就是要先知道其序列的長度 `L`。因為是要從結尾往前推的第 `n` 個結點來算，而不管是 two pointer 還是 one pass 都只是由這結果往回推算或是紀錄第 `n` 個節點而已。

這邊要特別提到的是，滿多人提到官方的解法不能算是 one pass，因為用到兩個迴圈。但是執行上我個人認為的確可以說是 one pass，他只是中間切斷放到另一個迴圈來跑。但這個定義就見仁見智了。

### 解法範例

#### Go

##### Two pointer

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{0, head}
	first := head
	length := 0

	for first != nil {
		length++
		first = first.Next
	}

	first = dummy
	for i := length - n; i > 0; i-- {
		first = first.Next
	}
	first.Next = first.Next.Next
	return dummy.Next
}
```

##### One pass

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{0, head}
	first := dummy
	second := dummy

	for i := 0; i <= n; i++ {
		first = first.Next
	}

	for first != nil {
		first = first.Next
		second = second.Next
	}
	second.Next = second.Next.Next
	return dummy.Next
}
```

#### JavaScript

##### Two pointer

```javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
    const dummy = new ListNode(0, head);
    let length = 0,
        first = head;
    while (first) {
        length++;
        first = first.next;
    }

    first = dummy;
    for (let i = length - n; i > 0; i--) {
        first = first.next;
    }

    first.next = first.next.next;
    return dummy.next;
};
```

##### One pass

```javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
    const dummy = new ListNode(0, head);
    let first = dummy,
        second = dummy;
    for (let i = 0; i < n + 1; i++) {
        first = first.next;
    }

    while (first !== null) {
        first = first.next;
        second = second.next;
    }

    second.next = second.next.next;
    return dummy.next;
};
```

#### Kotlin

##### Two pointer

```kotlin
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
        val dummy: ListNode = ListNode(0).apply { next = head }
        var first: ListNode? = head
        var length: Int = 0

        while (first!!.next != null) {
            length ++
            first = first!!.next
        }

        first = dummy
        for (i in (length - n) downTo 0) {
            first = first!!.next
        }

        first!!.next = first?.next?.next
        return dummy.next
    }
}
```

##### One pass

```kotlin
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
        val dummy: ListNode = ListNode(0).apply { next = head }
        var first: ListNode? = dummy
        var second: ListNode? = dummy

        for (i in 0 until n) {
            first = first!!.next
        }

        while (first!!.next != null) {
            first = first!!.next
            second = second!!.next
        }

        second!!.next = second?.next?.next
        return dummy.next
    }
}
```

#### PHP


##### Two pointer

```php
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution
{

    /**
     * @param ListNode $head
     * @param Integer $n
     * @return ListNode
     */
    function removeNthFromEnd($head, $n)
    {
        $dummy = new ListNode(0, $head);
        $first = $head;
        $length = 0;
        while (!is_null($first)) {
            $length++;
            $first = $first->next;
        }

        $first = $dummy;
        for ($i = $length - $n; $i > 0; $i--) {
            $first = $first->next;
        }

        $first->next = $first->next->next;
        return $dummy->next;
    }
}
```

##### One pass

```php
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution
{

    /**
     * @param ListNode $head
     * @param Integer $n
     * @return ListNode
     */
    function removeNthFromEnd($head, $n)
    {
        $dummy = new ListNode(0, $head);
        $first = $dummy;
        $second = $dummy;

        for ($i = 0; $i < $n + 1; $i++) {
            $first = $first->next;
        }

        while (!is_null($first)) {
            $first = $first->next;
            $second = $second->next;
        }

        $second->next = $second->next->next;
        return $dummy->next;
    }
}
```

#### Python


##### Two pointer

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution:
    def removeNthFromEnd(self, head: ListNode | None, n: int) -> ListNode | None:
        dummy: ListNode = ListNode(0, head)
        length: int = 0
        first: ListNode = head
        while first is not None:
            length += 1
            first = first.next

        first = dummy
        for _ in range(length - n, 0, -1):
            first = first.next

        first.next = first.next.next
        return dummy.next
```

##### One pass

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution:
    def removeNthFromEnd(self, head: ListNode | None, n: int) -> ListNode | None:
        dummy: ListNode = ListNode(0, head)
        first: ListNode = dummy
        second: ListNode = dummy

        for _ in range(n + 1):
            first = first.next

        while first is not None:
            first = first.next
            second = second.next

        second.next = second.next.next
        return dummy.next
```

#### Rust

```rust
```

#### Swift

##### Two pointer

```swift
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */


class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        guard let head = head else { return nil }

        let dummy = ListNode(0, head)
        var length: Int = 0
        var first: ListNode? = head

        while first != nil {
            length += 1
            first = first?.next
        }

        first = dummy
        for _ in 0..<(length - n) {
            first = first?.next
        }

        first!.next = first?.next?.next
        return dummy.next
    }
}
```

##### One pass

```swift
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */

class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        guard let head = head else { return nil }

        let dummy = ListNode(0, head)
        var first: ListNode? = dummy
        var second: ListNode? = dummy

        for _ in 0...n {
            first = first?.next
        }

        while first != nil {
            first = first?.next
            second = second?.next
        }

        second!.next = second?.next?.next
        return dummy.next
    }
}
```