19. 删除链表的倒数第N个节点

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

示例：

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

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

说明：

给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？

方法1——计算长度

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        length = 0
        cur = head
        while cur:
            length += 1
            cur = cur.next
        length = length-n
        cur = head
        l = 0
        if l == length:
            return head.next
        while l < length-1:
            cur = cur.next
            l += 1
        cur.next = cur.next.next
        return head

方法2——双指针

对法1的优化，让两个指针保持n的距离，并让其中一个指针到达第n个节点后同向移动，巧解本题。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        sentinel = ListNode(0)
        sentinel.next = head
        first, second = sentinel, head
        for i in range(n-1):
            second = second.next
        while second and second.next:
            first = first.next
            second = second.next
        first.next = first.next.next
        return sentinel.next