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

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

在链表中，删除一个节点通常涉及到修改指向该节点的前驱节点的 next 指针。但是，如果我们要删除链表的倒数第 N 个节点，这个问题就变得更加复杂。因为我们需要先找到倒数第 N 个节点，然后再进行删除操作。

**解决方案**

我们的解决方案是使用两个指针来实现：一个快指针（fast pointer）和一个慢指针（slow pointer）。快指针会先走 N 步，然后慢指针就会从头开始追赶快指针。这样一来，当快指针到达链表的末尾时，慢指针就停留在倒数第 N 个节点处。

**代码示例**

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef removeNthFromEnd(head: ListNode, n: int) -> ListNode:
 # 创建快指针和慢指针 fast = head slow = head # 快指针先走 N 步 for _ in range(n):
 fast = fast.next # 慢指针从头开始追赶快指针 while fast is not None and fast.next is not None:
 fast = fast.next slow = slow.next # 如果快指针到达链表的末尾，说明慢指针停留在倒数第 N 个节点处 if fast is None:
 return head.next # 删除倒数第 N 个节点 slow.next = slow.next.next return head# 测试代码head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

n =2new_head = removeNthFromEnd(head, n)

while new_head is not None:
 print(new_head.val, end=" ")
 new_head = new_head.nextprint()