---
# System prepended metadata

title: Leetcode 19. Remove Nth Node From End Of List
tags: [Two Pointers, Linked List, Leetcode]

---

## 題解

### 雙指針 (不使用虛擬頭節點)

```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: Optional[ListNode], n: int) -> Optional[ListNode]:
        fast = slow = head
        while n > 0 and fast:
            fast = fast.next
            n -= 1
        if not fast: # 因為 n < sz 所以當 fast == None 就代表是要移除第一個
            return head.next
        while fast.next:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return head
```

### 雙指針 (使用虛擬頭節點)

```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: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode()
        dummy.next = head
        fast,slow = head, dummy
        for i in range(n):
            fast = fast.next
        # 加上了虛擬頭節點就不會有 fast == None 的問題
        while fast:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next
```