当前位置： 首页 > news >正文

个人网站备案名,抖音小程序权限怎么关闭,如何看网站是否正常,沧州新华区237.删除链表的节点 链表删除节点的本质是不用删除#xff0c;只需要操作指针#xff0c;跳过需要删除的节点#xff0c;指向下下一个节点即可#xff01; 删除某个节点#xff0c;但是不知道这个节点的前一个节点#xff0c;也不知道头节点#xff01;摘自力扣评论区…237.删除链表的节点 链表删除节点的本质是不用删除只需要操作指针跳过需要删除的节点指向下下一个节点即可 删除某个节点但是不知道这个节点的前一个节点也不知道头节点摘自力扣评论区如何让自己在世界上完全消失但是又不死将自己变成另一个人再杀了那个人将node.next的值赋给node再将node连接到node.next的next

Definition for singly-linked list.

class ListNode:

def init(self, x):

self.val x

self.next Noneclass Solution:def deleteNode(self, node)::type node: ListNode:rtype: void Do not return anything, modify node in-place instead.node.val node.next.val node.next node.next.next什么时候需要创建哨兵节点dummy node

一般来说如果需要删除头节点是需要dummy node作为辅助的 19.删除倒数第N个节点 这道题需不需要创建dummy node如果n等于链表长度那么n是会被删除的所以需要 常规思路找到正数第几个 先遍历一遍链表计算链表长度n这样就知道倒数第N个节点是正数的第n-N1个将第n-N节点指针指向n-N2即可 实现过程中有许多问题实现起来有点缝缝补补的意思

Definition for singly-linked list.

class ListNode:

def init(self, val0, nextNone):

self.val val

self.next nextclass Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:if n 0:return headcnt 0cur head # 指向头节点while cur:cnt 1cur cur.next# 处理n等于链表长度的情况即要删除头节点if n cnt:return head.nextc cnt - ncur headwhile c-1 0: # 走cnt - n步走到要删除节点的前一个节点cur cur.nextc - 1if cur.next:cur.next cur.next.nextreturn head————————————————————————————通过妙解前后指针

已知要删除倒数第N个节点初始化前指针先走N步然后初始化后指针一起向后走前后指针距离始终是N当前指针走到了最后一个倒数第一个则后指针就恰好走到了倒数第N1个节点

Definition for singly-linked list.

class ListNode:

def init(self, val0, nextNone):

self.val val

self.next nextclass Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:# 由于有可能需要删除倒数第n个即开头节点所以创建dummynodedummy ListNode(0)dummy.next head# 链表中用指针表示位置跟数组的指针之间用索引不同# 所以定义右指针指向dummyright dummy# 向右走n步for _ in range(n):right right.next# 左指针也指向dummyleft dummy# 一起向后走直到右指针走到头while right.next: # 不是right而是right.next,才是right走到倒数第一个right right.nextleft left.next# 开始正数 左1右n。结束右倒数第1左倒数第一N# 反正此时左要删除的节点的上一个节点left.next left.next.nextreturn head

———————————————————————— 解答错误 177 / 208 个通过的测试用例官方题解 输入 head [1] n 1添加到测试用例 输出 [1] 预期结果 []注意不是返回head而是dummy.next

Definition for singly-linked list.

class ListNode:

def init(self, val0, nextNone):

self.val val

self.next next

class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:# 由于有可能需要删除倒数第n个即开头节点所以创建dummynodedummy ListNode(0)dummy.next head# 链表中用指针表示位置跟数组的指针之间用索引不同# 所以定义右指针指向dummyright dummy# 向右走n步for _ in range(n):right right.next# 左指针也指向dummyleft dummy# 一起向后走直到右指针走到头while right.next: # 不是right而是right.next,才是right走到倒数第一个right right.nextleft left.next# 开始正数 左1右n。结束右倒数第1左倒数第一N# 反正此时左要删除的节点的上一个节点left.next left.next.nextreturn dummy.next删除排序链表中的重复元素 基本思路很简单逐渐遍历链表要么删除元素要么之间向后移动

Definition for singly-linked list.

class ListNode:

def init(self, val0, nextNone):

self.val val

self.next next

class Solution:def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]:dummy ListNode(None)dummy.next headslow headwhile slow:# 确保 fast 和 fast.next 不为 Noneif slow.next:fast slow.nextelse:breakwhile fast and fast.val slow.val:fast fast.nextslow.next fastslow slow.nextreturn dummy.next真的必须用到dummynode么有可能删除开头节点才必须用dummynode这里可以规避掉删开头节点这个问题只用一个cur指针可以完成任务

Definition for singly-linked list.

class ListNode:

def init(self, val0, nextNone):

self.val val

self.next next

class Solution:def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]:cur headwhile cur.next:if cur.val cur.next.val:cur.next cur.next.nextelse:cur cur.nextreturn head

执行出错 2 / 168 个通过的测试用例 AttributeError: NoneType object has no attribute next^^^^^^^^while cur.next: Line 9 in deleteDuplicates (Solution.py)^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ret Solution().deleteDuplicates(param_1) Line 43 in _driver (Solution.py)_driver() Line 58 in module (Solution.py)提示没处理空节点情况

Definition for singly-linked list.

class ListNode:

def init(self, val0, nextNone):

self.val val

self.next next

class Solution:def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]:if not head:return Nonecur headwhile cur.next:if cur.val cur.next.val:cur.next cur.next.nextelse:cur cur.nextreturn head

通过这道题是删除掉重复的节点只保留一个 下道题如果链表有重复节点全部删除只保留原本就不存在重复节点的节点 这道题很简单实现起来也应该很简单但我实在太菜…写了好久没写对最后看了答案 暂时没心情复盘复习的时候注意翻看力扣提交记录

Definition for singly-linked list.

class ListNode:

def init(self, val0, nextNone):

self.val val

self.next next

class Solution:def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]:# 重复节点可能出现在开头开头head有可能被删除# 所以定义dummynodedummy ListNode(None)dummy.next headcur dummywhile cur.next and cur.next.next : # 要的是val cur.next.val # 记下下一个节点值if cur.next.next.val val: # 如果下下个节点值等于val# 套一个循环只要当前节点的下一个节点值等于val就cur.next cur.n.n,来删掉下一个节点while cur.next and cur.next.val val :cur.next cur.next.nextelse: # cur的n和nn不相等——cur走一步cur cur.nextreturn dummy.next