leetcode [19] 删除链表的倒数第N个节点

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

由于直接快慢指针差距n移动的话，慢指针会落在要删除的节点，因此让n+1，这样可以落到删除节点的前一个节点。

注意的是，如果n没有走完，说明删除的是第一个节点，这里就直接特殊处理，返回第二个节点。如果删除的是最后一个节点，慢指针的的后面是空，要判断。

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        if n == 0:
            return None
        fast = head
        slow = head
        n += 1
        while n and fast:
            fast = fast.next
            n -= 1
        if n != 0:
            return head.next
        while fast:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next
        return head