难度: Medium
给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1 输出：[]
示例 3：
输入：head = [1,2], n = 1 输出：[1]
提示：
sz1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz进阶：能尝试使用一趟扫描实现吗？
注意：本题与主站 19 题相同： https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
运行时间: 20 ms
内存: 15.9 MB
# 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:
dummy = ListNode(0, head)
first = head
second = dummy
for i in range(n):
first = first.next
while first:
first = first.next
second = second.next
second.next = second.next.next
return dummy.next
这个题解采用了双指针（快慢指针）的方法来找到倒数第n个节点。首先，创建一个哑节点(dummy node)，这个节点的next指向链表的head，这样可以方便地处理边界情况，比如删除链表的头节点。算法首先将一个指针(first)向前移动n次，这样从first到链表末尾就会有n个节点。然后，同时移动两个指针（first和second），直到first指针到达链表末尾。这时，second指针会指向要删除节点的前一个节点。通过修改second的next指向，可以将倒数第n个节点从链表中删除。最后，返回dummy.next，即更新后的链表头节点。
时间复杂度: O(n)
空间复杂度: O(1)
# 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:
dummy = ListNode(0, head) # 创建一个哑节点，其next指向head
first = head # first指针初始指向head
second = dummy # second指针初始指向dummy，方便处理删除头节点的情况
for i in range(n):
first = first.next # 移动first指针n步
while first:
first = first.next # 同时移动first和second直到first到达末尾
second = second.next
second.next = second.next.next # 删除second的下一个节点，即倒数第n个节点
return dummy.next # 返回更新后的头节点
使用哑节点可以简化删除链表头节点的复杂度。没有哑节点，如果需要删除头节点，就必须单独处理这种边界情况，因为头节点没有前一个节点。引入哑节点后，不管是删除头节点还是其他节点，都可以统一通过修改前一个节点的next指针来实现。这样可以使代码更加简洁且易于维护。
当n等于链表长度时，第一个指针（first）会移动n步达到链表末尾的None。在这种情况下，第二个指针（second）仍然指向哑节点。因为哑节点的next指向原始头节点，移动second的next指针到next的next节点（即second.next = second.next.next）实际上会删除原始的头节点。因此，通过使用哑节点和适当移动第二个指针可以确保即使n等于链表长度时也能正确删除头节点。
是的，如果链表长度等于n，那么first指针移动n步后确实会变成None。在算法中，这种情况是合理的，因为接下来的while循环将不执行，因为first已经是None。这时，second指针位于哑节点位置，其next指向的是原链表的头节点。如前一个问题所述，通过将second.next指向second.next.next，可以删除原链表的头节点。这正是算法处理这种情况的方式。