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所指向的节点就可以了。(比较巧妙)
思路是这样的,但要注意一些细节。
分为以下几步:
- 定义虚拟节点
- 定义fast指针和slow指针,初始值为虚拟头结点,如图:
- fast首先走n + 1步 ,为什么是n+1呢,因为只有这样同时移动的时候slow才能指向删除节点的上一个节点(方便做删除操作),如图:
- fast和slow同时移动,直到fast指向末尾,如图:
注意是 fast为None 而不是 fast.next 为None
- 删除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/