从链接列表中删除该值

Question

给定链表的头和一个整数val，移除链表中所有具有Node.val==val的节点，并返回新的头

class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
#Checking if head is empty
if (head == None):
return head

prev = head
curr = head
while curr:
if curr.val == val:
if curr == prev:
head = head.next
prev = prev.next

else:
prev.next = curr.next
else:

if curr != prev:
prev = prev.next
curr = curr.next
return head`
``

Answer 1

主要问题是您的最终return head是while循环的一部分，因此该循环只会迭代一次。通过将该语句移出循环(减少缩进(来解决此问题。

有了这个修复，它就会起作用。

其他备注

• 将prev初始化为head有点尴尬。这意味着当head节点从列表中删除时，需要保持更新。我建议将prev初始化为None
• 没有必要单独处理空列表的情况。在这种情况下，循环不会迭代，因此在函数开头没有if语句的情况下，您将获得预期的结果
• 在外部else块中，当您只执行prev = curr时，不需要if

代码

class Solution:
def removeElements(self, head, val):
prev = None  # Initialise like this
curr = head
while curr:
if curr.val == val:
if not prev:
head = curr.next
else:
prev.next = curr.next
else:
prev = curr
curr = curr.next
return head  # Not part of the loop

另一个想法是首先处理头节点之后的删除。最后检查是否必须保留第一个节点。然后代码可以变成：

class Solution:
def removeElements(self, head, val):
curr = head
while curr.next:
if curr.next.val == val:
curr.next = curr.next.next
else:
curr = curr.next
return head.next if head and head.val == val else head

使用递归，它可能看起来像这样：

class Solution:
def removeElements(self, head, val):
if not head:
return head
head.next = self.removeElements(head.next, val)
return head.next if head.val == val else head