给定一个链表的头节点 head 和一个整数 val ,请删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
例如:
原链表转换为列表:[1, 2, 6, 3, 4, 5, 6],要删除的链表元素 val = 6
最终的链表转换为列表:[1, 2, 3, 4, 5]原链表转换为列表:[],要删除的链表元素 val = 1
最终的链表转换为列表:[]原链表转换为列表:[7, 7, 7, 7],要删除的链表元素 val = 7
最终的链表转换为列表:[]
已知 链表节点的定义、链表与列表相互转换 的代码如下:
class ListNode: # 单链表 def __init__(self, val=0, next=None): self.val = val # 链表节点上存储的元素 self.next = next # 指向下一个链表节点 def list_to_list_node(numbers): # 将列表转换为单向链表,并返回链表的头节点 dummy_head = ListNode(0) pre = dummy_head for number in numbers: pre.next = ListNode(number) pre = pre.next pre = dummy_head.next return pre def list_node_to_list(node): # 将单向链表转换为列表 result = [] while node: result.append(node.val) node = node.next return result
dummy_head
,然后再进行链表节点的删除next
指向下个节点的下个节点,同时注意此时不能让当前节点 cur
向后移动,因为 下个节点的下个节点 cur.next.next
很可能也符合条件,所以需继续循环dummy_head.next
def removeElements(head: ListNode, val: int) -> ListNode: dummy_head = ListNode(next=head) # 设置一个虚拟头节点 cur = dummy_head while cur.next is not None: if cur.next.val == val: # 如果满足条件,则让下一个节点指向下下个节点 cur.next = cur.next.next else: cur = cur.next new_head = dummy_head.next # 新的头节点为虚拟头节点的下一个节点 return new_head
next
指向下个节点的下个节点,同时注意此时不能让当前节点 cur
向后移动,因为 下个节点的下个节点 cur.next.next
很可能也符合条件,所以需继续循环def removeElements(head: ListNode, val: int) -> ListNode: while head is not None and head.val == val: # 删除符合条件的所有头节点 head = head.next cur = head while cur is not None and cur.next is not None: # 删除符合条件的所有其他节点 if cur.next.val == val: # 如果满足条件,则让下一个节点指向下下个节点 cur.next = cur.next.next else: cur = cur.next return head
更多Python编程题,等你来挑战:Python编程题汇总(持续更新中……)