编写不带头结点的单链表删除算法,完成的功能为:删除单链表head中第i个元素,并用x返回其值。
时间: 2024-09-30 12:06:25 浏览: 32
在不使用头结点的单链表中删除第i个节点可以分为以下几个步骤:
1. **初始化**:如果链表为空或者i小于1,直接返回null表示无法删除。
2. **遍历查找前i-1个节点**:创建两个指针,`current` 和 `prev`,分别用于当前节点和前一个节点。`prev` 初始设为 null,然后从头开始移动 `current`,直到找到第 i - 1 个节点,同时更新 `prev` 为 `current`。
3. **定位目标节点**:在找到了第 i - 1 个节点之后,将 `current` 指向第 i 个节点。
4. **删除目标节点**:如果 `current` 不为 null,则删除 `current` 节点。这通常通过设置 `prev.next` 为 `current.next` 来实现,因为我们要让 `prev` 的下一个节点指向 `current` 的下一个节点,跳过 `current`。
5. **返回值**:如果成功删除了节点,就返回 `current.value`;如果没有找到第 i 个节点(即 `current` 仍为 null),则说明链表太短,无法删除第 i 个元素,也返回 x。
下面是一个简单的 Python 示例:
```python
def delete_node(head, i, x):
if head is None or i <= 0:
return x
current = head
prev = None
for _ in range(i - 1):
if current is None:
return x
prev = current
current = current.next
if current is not None:
prev.next = current.next
else:
print(f"Error: Cannot delete element at index {i}, as the list only has {i - 1} elements.")
# Return the value of the deleted node (if it exists)
if current is not None:
return current.value
# 使用示例
# 删除链表中第3个节点
head = Node(1, Node(2, Node(3, Node(4, Node(5)))))
deleted_value = delete_node(head, 3, "x") # 返回 3
```
阅读全文