問題19：給定一個鏈表，刪除鏈表的倒數(shù)第n個節(jié)點切省，并且返回鏈表的頭結(jié)點。
先思考另一道題：給定一個鏈表帕胆，輸出鏈表的倒數(shù)第n個節(jié)點朝捆。
用快慢指針，快指針先走n步懒豹，然后慢指針和快指針同速搜索芙盘。當(dāng)快指針指向鏈表末尾None的時候，慢指針恰好指向鏈表倒數(shù)第n個節(jié)點脸秽。下圖以n=2為例儒老。
有了這個思考做基礎(chǔ)，刪除倒數(shù)第n個節(jié)點就不難了记餐，只需要讓fast指針提前停止一位驮樊，則slow指針的停止位置是倒數(shù)第n+1個節(jié)點，直接slow.next = slow.next.next片酝，就把倒數(shù)第n個節(jié)點刪除了囚衔。
完整代碼：
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if not head:
return head
fast, slow = head, head
for i in range(n):
if fast == None:
return None
fast = fast.next
if not fast:
return head.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return head
運行結(jié)果：
