Python编程题45--移除链表元素
2022-01-16 本文已影响0人
wintests
题目
给定一个链表的头节点 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
实现思路1
- 设置一个虚拟头节点
dummy_head，然后再进行链表节点的删除 - 对链表节点进行遍历，如果下一个节点符合条件，那么就让则让下一个节点向后移动一位，也就是让下一个节点的
next指向下个节点的下个节点，同时注意此时不能让当前节点cur向后移动，因为 下个节点的下个节点cur.next.next很可能也符合条件，所以需继续循环 - 如果下一个节点不满足条件时，那么才让当前节点向后移动一位
- 最后返回头节点时，需要注意新的头节点是 dummy_head 的下一个节点，即
dummy_head.next
代码实现1
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
实现思路2
- 不设置虚拟头节点，直接用原链表进行节点的删除
- 对于符合条件的节点，在删除节点的时候，这里需区分头节点和非头节点的情况，二者的处理方式不一样
- 首先需要处理符合条件的链表头节点，如果链表头节点符合条件，那么直接让头节点向后移动一位，循环该操作，直到其不再满足条件
- 接着处理非头节点的情况，如果下一个节点符合条件，那么就让则让下一个节点向后移动一位，也就是让下一个节点的
next指向下个节点的下个节点，同时注意此时不能让当前节点cur向后移动，因为 下个节点的下个节点cur.next.next很可能也符合条件，所以需继续循环 - 最后在下一个节点不满足条件时，那么才让当前节点向后移动一位
代码实现2
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编程题汇总（持续更新中……）
