題目描述

給定一個鏈表，刪除鏈表的倒數(shù)第 n 個節(jié)點，并且返回鏈表的頭結(jié)點。

示例：

給定一個鏈表: 1->2->3->4->5, 和 n = 2.

當刪除了倒數(shù)第二個節(jié)點后，鏈表變?yōu)?1->2->3->5.
說明：

給定的 n 保證是有效的。

進階：

你能嘗試使用一趟掃描實現(xiàn)嗎？

思路

設置快慢指針，快指針先走2步，慢指針再同步遍歷
快指針為空，進行刪除。

class ListNode:
    def __init__(self, val=0):
        self.next = None
        self.val = val
class Solution:
    def removeNthFromEnd(self, head, n):
        if not head:
            return None
        dummy = ListNode(0)
        dummy.next = head
        fast = dummy
        slow = dummy
        # 走n+1步
        while n >= 0:
            fast = fast.next
            n -= 1
        # 當fast為空退出
        while fast:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next

AC19