###### tags: `Leetcode` `medium` `list` `python` `Top 100 Liked Questions`

# 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 ```nth``` node from the end of the list and return its head.


**Example 2:**

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

**Example 3:**

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

#### [圖片來源:] https://leetcode.com/problems/remove-nth-node-from-end-of-list/

## 解題想法:
* 要求刪掉從尾數第N個node
* 使用兩pointer
* slow=head
* fast=head
* **讓fast先走N步**
* 兩pointer一起移動直到fast到尾
* 此時**slow的下一個即為要刪除的node**
* slow.next=slow.next.next

## Python:

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def insert(self,node):
        if self.next==None:
            self.next=ListNode(node)
        else:
            self.next.insert(node)
    def printList(self):
        head = self
        res=[]
        while head:
            res.append(head.val)
            head=head.next
        print(res)
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        #兩個pointer: fast slow
        fast = head
        slow = head
        for i in range(n):
            fast = fast.next
        #特殊case: 若只有一值:
        if not fast:
            return head.next
        #要判斷fast.next，才能讓fast最終停在尾
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next= slow.next.next
        return head

        
if __name__ == '__main__':
    head = ListNode(1)
    head.insert(2)
    head.insert(3)
    head.insert(4)
    head.insert(5)
    head.printList()
    result = Solution()
    ans=result.removeNthFromEnd(head,2)
    ans.printList()