203.删除链表元素
题目描述
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
思路
1.递归
链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。
对于给定的链表，首先对除了头节点 head 以外的节点进行删除操作，然后判断 head 的节点值是否等于给定的 val。如果 head 的节点值等于 val，则 head 需要被删除，因此删除操作后的头节点为 head.next；如果 head 的节点值不等于 val，则 head\ 保留，因此删除操作后的头节点还是 head。
递归的终止条件是 head 为空，此时直接返回 head。当 head 不为空时，递归地进行删除操作，然后判断 head 的节点值是否等于 val 并决定是否要删除 head。
2.迭代
用 temp 表示当前节点。如果 temp 的下一个节点不为空且下一个节点的节点值等于给定的 val，则需要删除下一个节点。删除下一个节点可以通过以下做法实现：
temp.next=temp.next.next
如果 temp 的下一个节点的节点值不等于给定的 val，则保留下一个节点，将 temp 移动到下一个节点即可。
当 temp 的下一个节点为空时，链表遍历结束，此时所有节点值等于 val 的节点都被删除。
具体实现方面，由于链表的头节点 head 有可能需要被删除，因此创建哑节点 dummyHead，令 dummyHead.next=head，初始化 temp=dummyHead，然后遍历链表进行删除操作。最终返回 dummyHead.next 即为删除操作后的头节点。
代码
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def removeElements(self, head, val):
"""
移除单链表head中所有值为val的节点（迭代法）
时间复杂度：O(n)
空间复杂度：O(1)
:type head: ListNode
:type val: int
:rtype: ListNode
"""
# # 为单链表怎加一个头节点
# head_node = ListNode()
# head_node.next = head
#
# # 定义工作指针p和工作指针的前一个节点指针prev
# prev = head_node # prev指向头节点
# p = prev.next # p指向链表的第一个节点
#
# while p is not None:
# if p.val == val:
# prev.next = p.next
# p = p.next
# else:
# prev = p
# p = p.next
#
# return head_node.next
dummyHead = ListNode()
dummyHead.next = head
temp = dummyHead
while temp.next is not None:
if temp.next.val == val:
temp.next = temp.next.next
else:
temp = temp.next
return dummyHead.next
def removeElements1(self, head, val):
"""
移除单链表head中所有值为val的节点（递归法）
时间复杂度：O(n)
空间复杂度：O(n)
:param head:
:param val:
:return:
"""
if head is None:
return head
head.next = self.removeElements1(head.next, val)
return head.next if head.val == val else head
def create_linked_list(self, list):
"""根据list中的所有元素构建单链表"""
l = ListNode() # 单链表头节点
r = l # 起始尾指针r指向头节点
for e in list:
node = ListNode(e)
r.next = node
r = r.next
return l.next
def print_linked_list(self, linked_list) -> None:
"""
打印单链表中的所有元素
:param linked_list: 单链表
:return: 无
"""
print("----------------------------------------")
pointer = linked_list
while pointer is not None:
print(pointer.val)
pointer = pointer.next
if __name__ == "__main__":
slt = Solution()
linked_list = slt.create_linked_list([1, 2, 6, 3, 4, 5, 6])
# linked_list = slt.create_linked_list([7, 7, 7, 7])
slt.print_linked_list(linked_list)
deleted_linked_list = slt.removeElements1(linked_list, 6)
slt.print_linked_list(deleted_linked_list)