【链表】【删除节点】【刷题笔记】【灵神题单】

237.删除链表的节点

# 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个节点

常规思路：找到正数第几个

• 先遍历一遍链表，计算链表长度n
• 这样就知道倒数第N个节点，是正数的第n-N+1个
• 将第n-N节点指针，指向n-N+2即可！
  实现过程中有许多问题，实现起来有点缝缝补补的意思！

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         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
• 当前指针走到了最后一个，倒数第一个，则后指针就恰好走到了倒数第N+1个节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         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, val=0, next=None):
#         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, val=0, next=None):
#         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, val=0, next=None):
#         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, val=0, next=None):
#         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, val=0, next=None):
#         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