給你一個連結清單，删除連結清單的倒數第
n
個結點，并且傳回連結清單的頭結點。
示例1:
輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]
示例 2：
輸入：head = [1], n = 1
輸出：[]
示例 3：
輸入：head = [1,2], n = 1
輸出：[1]
提示：
連結清單中結點的數目為 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
進階：你能嘗試使用一趟掃描實作嗎？
【分析】
示例1給出的連結清單結構如下圖所示：
要删除連結清單中的某個節點，需要知道其前一個節點。對于頭節點來說，其沒有前一個節點，是以，需要定義虛拟頭節點，如下圖：
這裡要删除的是連結清單中倒數第2個節點，其前一個節點是指針slow指向的節點：
那如何确定slow指向的位置呢？在這裡還需要引入指針fast，當指針fast指向null時，它與指針slow之間相差兩個節點，剛好等于n(n=2)的值:
那麼又如何确定fast的位置呢？由于我們隻知道連結清單的頭節點，要找到待删除的節點，就需要從頭節點開始周遊連結清單。是以，定義慢指針slow和快指針fast，其初始都指向虛拟頭節點。然後，我們先讓快指針fast向前移動n+1步。示例中n=2，是以fast向前移動n+1=3步：
此時，讓慢指針和快指針同時向前移動，每次移動一步，直到快指針fast指向null：
這時，慢指針slow所指節點的下一個節點就是待删除節點：
接着，隻需将slow所指節點的後繼指針指向待删除節點的下一個節點，然後待删除節點delNode的後繼指針指向null，即可将倒數第二個節點删除，或者直接slow.next = slow.next.nex即可：
# 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, n: int) -> ListNode:
dummyHead = ListNode(0, head)
fast, slow = dummyHead, dummyHead
for i in range(n+1):
fast = fast.next
# another version(faster actually).
# fast, slow = head, dummyHead
# for i in range(n):
# fast = fast.next
while fast != None:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
# delNode = slow.next
# slow.next = delNode.next
# delNode.next = None
return dummyHead.next
# 複雜度分析
# 時間複雜度：O(L)，其中 L 是連結清單的長度。
# 空間複雜度：O(1)。 天雨雖寬，不潤無根之草。
佛門雖廣，不渡無緣之人。