给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5]
输入:head = [1], n = 1 输出:[]
输入:head = [1,2], n = 1 输出:[1]
length
。pos
。这个思路的关键点是使用双指针的技巧。通过快指针先向前移动n步,可以使得快指针和慢指针之间相差n个节点。然后同时移动快指针和慢指针,直到快指针到达链表的末尾。这样,慢指针所指向的节点就是要删除的节点的前一个节点。
通过这种方法,我们可以在一次遍历中找到要删除的节点的前一个节点,并进行删除操作,而不需要遍历两次链表来实现。
dummy
,并将它指向原链表的头结点 head
。fast
和 slow
,初始时都指向虚拟头结点。fast
先向前移动 n 步,即 for i in range(n+1): fast = fast.next
。fast
到达链表的末尾。使用循环 while fast:
,循环内部的操作为 fast = fast.next
和 slow = slow.next
。slow
所指向的节点就是要删除的节点的前一个节点。slow
所指向的节点的 next
指针指向下一个节点的 next
指针,即 slow.next = slow.next.next
,实现删除倒数第 n 个节点。dummy.next
,即为新链表的头结点。class Solution(object):
def removeNthFromEnd(self, head, n):
dummy = ListNode(0) # 创建一个虚拟头结点,值为0
dummy.next = head # 将虚拟头结点指向原链表的头结点
fast = dummy # 快指针初始指向虚拟头结点
slow = dummy # 慢指针初始指向虚拟头结点
for i in range(n+1): # 快指针先向前移动n步(包括虚拟头结点)
fast = fast.next
while fast: # 同时移动快指针和慢指针,直到快指针到达链表末尾
fast = fast.next # 快指针每次移动一步
slow = slow.next # 慢指针每次移动一步
slow.next = slow.next.next # 删除倒数第n个节点,将慢指针指向的节点的next指针指向下一个节点的next指针
return dummy.next # 返回链表的头结点
class Solution(object):
定义一个名为Solution
的类。
def removeNthFromEnd(self, head, n):
定义了一个名为removeNthFromEnd
的方法,该方法接受两个参数:head
表示链表的头结点,n
表示要删除的倒数第n个节点。
dummy = ListNode(0)
创建一个名为dummy
的虚拟头结点,值为0。
dummy.next = head
将虚拟头结点的next
指针指向原链表的头结点,以便建立虚拟头结点与原链表的连接。
fast = dummy
slow = dummy
初始化快指针fast
和慢指针slow
,都指向虚拟头结点。
for i in range(n+1):
fast = fast.next
快指针先向前移动n步(包括虚拟头结点),以建立快慢指针之间的n个节点的距离。
while fast:
fast = fast.next
slow = slow.next
同时移动快指针和慢指针,快指针每次向前移动一步,慢指针每次向前移动一步,直到快指针到达链表末尾。
slow.next = slow.next.next
删除倒数第n个节点,即将慢指针指向的节点的next
指针指向下一个节点的next
指针。通过跳过要删除的节点实现删除操作。
return dummy.next
返回链表的头结点,即虚拟头结点的下一个节点,用于处理删除头结点的情况。