【題目】

給定一個鏈表，刪除鏈表的倒數第 n 個節點，并且返回鏈表的頭結點。

示例：
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當刪除了倒數第二個節點后，鏈表變為 1->2->3->5.

說明：
給定的 n 保證是有效的。

進階：
你能嘗試使用一趟掃描實現嗎？

【思路】

解法一：遍歷鏈表，得到鏈表長度N。那么刪除倒數第n個節點，即為刪除第N - n個節點。找到第N - n -1個節點，記為p，q = p.next, p.next=p.next.next, del p（記得清除內存）。

唯一的問題是：如何刪除第1個元素，需要單獨判斷？可以不用這么麻煩：增加一個無意義的頭結點，所有的刪除邏輯都變成一致的了！

解法二：使用兩個指針first和second遍歷鏈表，首先，first指針前進n步，second指針不變；緊接著，first指針和second指針同時前進，直到first.next為None。此時，second指針指向的是倒數第n+1個節點，second.next = second.next.next同時刪除無用內存即可。（刪除第1個元素的代碼邏輯與其它元素的不一樣，解決方法參考解法一的說明。）

【代碼】

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, n: int) -> ListNode:
        # 增加空的頭結點，使得邏輯一致
        node = ListNode(val=0, next=head)
        head = node
        
        # 找到第n-1個節點
        count = 0
        p = head
        while count < n:
            count += 1
            p = p.next
        
        # 找到倒數第n+1個節點
        q = head
        while p.next:
            p = p.next
            q = q.next
        
        # 刪除倒數第n個節點
        r = q.next
        q.next = q.next.next
        del r
        return head.next