难度: 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]
提示：
- 链表中结点的数目为
sz 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
Submission
运行时间: 48 ms
内存: 16.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: Optional[ListNode], n: int) -> Optional[ListNode]:
if head.next is None:
return
f = s = head
for _ in range(n):
f = f.next
if f is None:
return head.next
while f.next:
f = f.next
s = s.next
s.next = s.next.next
return head
Explain
该题解使用了快慢指针的方法。首先让快指针先走 n 步，然后快慢指针同时向前移动，直到快指针到达链表尾部。此时慢指针指向的就是倒数第 n 个节点的前一个节点，把慢指针的 next 指针指向 next.next，即可删除倒数第 n 个节点。特殊情况是如果快指针走了 n 步后为 None，说明要删除的是头节点，直接返回 head.next 即可。
时间复杂度: O(m)，其中 m 为链表的长度
空间复杂度: O(1)
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
if head.next is None: # 如果链表只有一个节点
return
f = s = head # 快慢指针初始化
for _ in range(n): # 快指针先走 n 步
f = f.next
if f is None: # 如果快指针走了n步后为None，说明要删除的是头节点
return head.next
while f.next: # 快慢指针同时向前，直到快指针到达尾部
f = f.next
s = s.next
s.next = s.next.next # 删除倒数第 n 个节点
return head
Explore
在使用快慢指针删除链表的倒数第n个节点时，让快指针先行n步是为了创建n+1个节点的间隔。这样，当快指针到达链表的末尾时，慢指针将正好位于倒数第n个节点的前一个节点。这个间隔确保了当我们修改慢指针的next指针来删除节点时，我们可以直接访问并修改正确的节点。
快指针在走完n步后如果到达None，这意味着链表的长度正好等于n。在这种情况下，要删除的节点正是头节点，因为从头节点开始到链表的末尾正好是n个节点。因此，如果快指针在走n步后是None，我们直接返回head.next，即可删除头节点。
慢指针必须指向倒数第n个节点的前一个节点，因为链表的删除操作需要修改目标节点的前一个节点的next指针。如果慢指针直接指向倒数第n个节点，我们将无法访问前一个节点的next指针来进行删除操作，因为单向链表不允许向后访问。
在代码中处理特殊情况，如链表长度等于1或n等于链表长度时，如果链表只有一个节点或快指针在前进n步后变为None（即链表长度等于n），则直接返回head.next，从而删除头节点。这些情况都是在算法的开始部分特别检查和处理的。
该算法的空间复杂度为O(1)，因为在执行删除操作时，无论链表的大小如何，我们只需要常数空间来存储固定数量的变量（即两个指针f和s）。这些指针不随链表的大小增加而增加，因此空间使用是固定的，不依赖于输入数据的规模。
如果快慢指针方法在某个测试用例中失败了，我会首先确认链表的长度和要删除的节点数n是否被正确处理。接着，我会检查边界条件，如链表只有一个节点或n等于链表长度的情况。最后，我会通过在每一步打印出快慢指针的位置和它们所指向的节点，来确保指针正确移动，并且正确的节点被标记为删除。