标签: 链表
难度: Easy
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
示例 1:
输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], val = 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明：
free 或 delete 被删除的节点运行时间: 48 ms
内存: 15.3 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
dummy = ListNode(0)
dummy.next = head
pre = dummy
cur = head
while cur:
if cur.val == val:
pre.next = pre.next.next
else:
pre = pre.next
cur = pre.next
return dummy.next
该题解采用了一个虚拟头节点(dummy node)的技巧来简化删除操作。首先，创建了一个虚拟头节点并将其指向真正的头节点。然后，使用两个指针，'pre'（前驱节点）和'cur'（当前节点），'pre'初始化为虚拟头节点，'cur'初始化为头节点。遍历链表，比较当前节点的值与目标值。如果相等，通过修改前驱节点的next指针来跳过当前节点，从而实现删除操作。如果当前节点的值不等于目标值，则同时移动两个指针前进。这样，当遍历完成后，链表中所有等于目标值的节点都会被删除。最后返回虚拟头节点的下一个节点，即更新后的链表头节点。
时间复杂度: O(n)
空间复杂度: O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
dummy = ListNode(0) # 创建虚拟头节点
dummy.next = head # 将虚拟头节点指向实际的头节点
pre = dummy # 前驱节点
cur = head # 当前节点
while cur: # 遍历链表
if cur.val == val: # 如果当前节点是目标节点
pre.next = pre.next.next # 删除当前节点
else:
pre = pre.next # 移动前驱节点
cur = pre.next # 移动当前节点
return dummy.next # 返回更新后的头节点
使用虚拟头节点可以简化链表操作，特别是在涉及头节点的增加或删除时。首先，它消除了需要单独处理头节点的情况，因为无论是否删除头节点，操作方法保持一致，即调整虚拟头节点的next指针。其次，这样做可以避免在删除节点时对空链表进行额外的检查，因为虚拟头节点保证了链表的非空性，简化了代码的逻辑和边界条件处理。
在链表中删除节点时，关键操作是将前驱节点的next指针指向当前节点的下一个节点，从而跳过当前节点实现删除。当前节点的next指针无需处理，因为一旦当前节点被前驱节点跳过，它就不再是链表的一部分，自然会被垃圾回收机制处理。这样做简化了操作，避免了对当前节点的额外处理，提高了代码的效率和清晰度。
此方法使用虚拟头节点，使得所有节点的删除操作，包括头节点，都具有统一的处理逻辑。即使目标节点是原始头节点，操作也是将虚拟头节点的next指针指向原始头节点的next节点，这样原始头节点就被有效删除。虚拟头节点确保了即使头节点被删除，链表的结构仍然完整，返回虚拟头节点的next即可获得新的头节点。
这种处理方式是为了确保连续的目标节点都能被正确删除。当一个节点被删除后，pre指针保持不变，因为可能存在连续的要删除的节点，而cur指针更新到pre.next确保了下一个节点可以被检查。如果移动了pre指针，有可能会跳过紧跟在被删除节点后的目标节点。因此，这种逻辑确保了每个节点都会被检查，没有节点被跳过。