2024年4月30日发(作者：)

程序设计链表改错题

题目：给定一个链表，删除链表的倒数第n个节点。

链表节点的定义如下：

python

复制代码

class ListNode:

def __init__(self, x):

= x

= None

示例：

输入：链表1->2->3->4->5，n = 2

输出：链表1->2->3->5

注意：给定的链表节点数大于等于n，且n为正整数。

错误的代码示例：

python

复制代码

def removeNthFromEnd(head, n):

dummy = ListNode(0) # 创建一个虚拟头节点

= head # 将虚拟头节点指向链表的头部

fast = slow = dummy # 初始化快指针和慢指针，都指向虚拟头节点

for _ in range(n): # 快指针先向前移动n步

fast =

while : # 当快指针到达链表末尾时，慢指针和快指针同时向前移动

fast =

slow =

= # 删除慢指针指向的节点

return # 返回修改后的链表的头部

上述代码中存在一个逻辑错误，当快指针到达链表末尾时，慢指针并不一定指向倒数第

n个节点。我们需要调整快指针和慢指针的移动策略，确保它们始终保持相隔n个节点

的距离。以下是修改后的代码：

python

复制代码

def removeNthFromEnd(head, n):

dummy = ListNode(0) # 创建一个虚拟头节点

= head # 将虚拟头节点指向链表的头部

fast = slow = dummy # 初始化快指针和慢指针，都指向虚拟头节点

for _ in range(n): # 快指针先向前移动n步

fast =

while : # 当快指针到达链表末尾时，慢指针继续向前移动，快指针

停止移动

slow =

fast =

= # 删除慢指针指向的节点

return # 返回修改后的链表的头部

这样，无论链表长度如何变化，快指针和慢指针始终保持相隔n个节点的距离，能够正

确删除倒数第n个节点。