上海网站设计工作室深圳哪里做网站

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

给你一个链表，删除链表的倒数第 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]

我的思路

删除倒数第n个节点，问题就在于如何去定位这倒数第n个，从前到后就是需要有个索引，但现在问题在于链表总的长度并不知道，所以需要第一步先去找到链表的长度：通过定义一个size，然后对链表进行遍历，逐渐加1，获取链表长度。然后定义索引为index=size-n。再遍历到索引处，执行删除。

class ListNode(object):def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution(object):def removeNthFromEnd(self, head, n):""":type head: ListNode:type n: int:rtype: ListNode"""dummy_node = ListNode(next=head)cur = dummy_nodesize = 0 # 链表长度while cur.next:cur = cur.nextsize += 1temp = dummy_nodeindex = size - nfor i in range(index):temp = temp.nexttemp.next = temp.next.nextreturn dummy_node.next

进阶：你能尝试使用一趟扫描实现吗？
可以用快慢指针法。
双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。（比较巧妙）
思路是这样的，但要注意一些细节。
分为以下几步：

1. 定义虚拟节点
2. 定义fast指针和slow指针，初始值为虚拟头结点，如图：

3. fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：

4. fast和slow同时移动，直到fast指向末尾，如图：

注意是 fast为None 而不是 fast.next 为None

5. 删除slow指向的下一个节点，如图：

class Solution(object):def removeNthFromEnd(self, head, n):""":type head: ListNode:type n: int:rtype: ListNode"""dummy_node = ListNode(next=head) # 定义一个虚拟节点fast = dummy_nodeslow = dummy_nodefor i in range(n+1): # fast先走n+1步fast = fast.nextwhile fast != None: # fast和slow同时走fast = fast.nextslow = slow.nextslow.next = slow.next.nextreturn dummy_node.next

本文文字及图片参考：https://programmercarl.com/