给定一个单链表A删除值大于Val(Val是用户的输入参数,其值可以和链表中元素相同也可以不同)的所有元素。 (1)完成链表的初始化; (2)完全给定元素的删除; (3)输出删除元素后的链表。
时间: 2024-09-11 21:17:57 浏览: 39
算法:给定一个链表,判断链表中是否存在环
在给定的问题中,你需要编写一个程序来处理一个单链表,具体步骤如下:
1. **链表初始化**:
首先,你需要创建一个Node类,它包含两个属性:`value`表示节点的值,`next`指向下个节点。然后你可以定义一个函数如 `initialize_list(A: List[int], val: int)` 来初始化链表。这个函数接收一个整数列表作为输入,遍历列表并将每个元素构造成一个新的Node,将其连接起来形成链表。如果用户输入的`val`不在列表中,那么链表将保持原始状态。
```python
class Node:
def __init__(self, value):
self.value = value
self.next = None
def initialize_list(A: list[int], val: int) -> Node:
if not A:
return None
head = Node(A[0])
current = head
for num in A[1:]:
new_node = Node(num)
current.next = new_node
current = current.next
return head
```
2. **删除元素**:
创建一个名为 `delete_elements(head: Node, val: int)` 的函数,传入链表头节点和用户指定的值`val`。遍历链表,当找到值大于`val`的节点时,跳过该节点,并继续检查下一个节点。若遇到的节点值等于`val`,则更新该节点的前一个节点使其指向当前节点的下一个节点,即删除当前节点。
```python
def delete_elements(head: Node, val: int) -> Node:
current = head
prev = None
while current:
if current.value > val:
prev = current
elif current.value == val and prev is not None:
prev.next = current.next
else:
prev = current
current = current.next
return head
```
3. **输出链表**:
最后,为了打印删除元素后的链表,你可以定义一个辅助函数 `print_list(head: Node)`,它递归地遍历并打印链表的元素。
```python
def print_list(head: Node):
if head:
print(head.value, end=" -> ")
print_list(head.next)
else:
print("None")
# 示例用法
head = initialize_list([1, 3, 5, 7, 9, 3], 3)
deleted_head = delete_elements(head, 3)
print_list(deleted_head)
```
阅读全文