对给定的单链表 L ,设计一个算法,删除 L 中值为 x 的结点的直接前驱结点。
时间: 2024-10-05 22:01:54 浏览: 50
对于给定的单链表 L 和要删除的元素值 x,我们可以采用迭代或递归的方式来实现这个算法。这里是一个基于迭代的简单步骤描述:
1. 初始化两个指针,`prev` 用于指向当前节点的前一个节点,`current` 则指向当前节点。
2. 遍历链表:
- 如果 `current` 指向的节点值等于 x,那么我们需要删除它。
a. 如果 `prev` 为空,说明头节点就是要删除的目标,更新头节点为下一个节点(`head = current.next`)。
b. 否则,将 `prev` 的 `next` 指向 `current.next`,跳过已找到的节点及其后续部分。
c. 更新 `prev` 为当前节点,继续遍历。
- 当 `current` 不是 x 时,`prev` 和 `current` 都向前移动一位。
3. 遍历结束后,链表中值为 x 的节点已经被成功地从列表中删除了。
```python
def deleteNode(L, x):
prev = None
current = L.head
while current is not None:
if current.val == x:
if prev is None: # 删除头节点的情况
L.head = current.next
else:
prev.next = current.next
else:
prev = current
current = current.next
# 示例:
L = LinkedList() # 假设LinkedList类已经存在,包含head属性
deleteNode(L, x)
```
阅读全文