济南php网站开发,南京网站制作公司排名,百度右侧相关网站,现在个人做网站还能盈利19.删除链表的倒数第N个节点
给你一个链表#xff0c;删除链表的倒数第 n 个结点#xff0c;并且返回链表的头结点。 示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5], n 2 输出#xff1a;[1,2,3,5] 示例 2#xff1a;输入#xff1a;head [1], n 1 输出删除链表的倒数第 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获取链表长度。然后定义索引为indexsize-n。再遍历到索引处执行删除。
class ListNode(object):def __init__(self, val0, nextNone):self.val valself.next nextclass Solution(object):def removeNthFromEnd(self, head, n)::type head: ListNode:type n: int:rtype: ListNodedummy_node ListNode(nexthead)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步 为什么是n1呢因为只有这样同时移动的时候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: ListNodedummy_node ListNode(nexthead) # 定义一个虚拟节点fast dummy_nodeslow dummy_nodefor i in range(n1): # fast先走n1步fast fast.nextwhile fast ! None: # fast和slow同时走fast fast.nextslow slow.nextslow.next slow.next.nextreturn dummy_node.next
本文文字及图片参考https://programmercarl.com/
