链表的删除算法pta
时间: 2024-10-14 15:05:05 浏览: 9
链表的删除算法通常涉及三种情况:删除头节点、删除指定节点以及删除特定位置的节点。这里我会简要描述基本的单向链表删除操作:
1. 删除头节点(头插法):
- 如果链表为空,无需处理。
- 否则,将第二个节点赋值给头节点,并将其next指针设为原头节点的下一个节点。
2. 删除指定节点:
- 通过遍历找到需要删除的节点,记录其前驱节点。
- 将前驱节点的next指针指向该节点的下一个节点,使得前驱节点的下一个节点取代了目标节点的位置。
3. 删除特定位置的节点(已知索引):
- 检查索引是否合法(0-based),然后从头节点开始遍历,每经过一个节点就递增计数器。
- 当计数器等于目标索引时,执行删除指定节点的操作。
在实际编写代码时,需要注意边界条件(如空列表、目标节点不存在等)以及内存管理(避免内存泄漏)。以下是伪代码示例:
```cpp
Node* deleteNode(Node* head, int index) {
if (head == nullptr || index < 0)
return head;
Node* current = head;
for (int i = 0; i < index && current != nullptr; i++)
current = current->next;
if (current == nullptr)
return head;
// 删除当前节点
if (current->next != nullptr)
current->next = current->next->next;
else
// 如果要删除的是尾节点,更新头节点
if (current == head)
head = head->next;
free(current); // 如果是动态分配内存,释放它
return head;
}
```
阅读全文