数据结构:设有一个带头结点的单循环链表,请设计算法从这个链表中删除值为x的结点。若链表中没有值为x的结点,则打印“没有找到该结点”。
时间: 2023-05-29 10:02:49 浏览: 137
算法思路:
首先,我们需要遍历单循环链表,查找值为x的节点。因为链表是单向的,所以我们需要维护两个指针prev和curr,分别指向当前节点的前一个节点和当前节点。遍历过程中,如果找到了值为x的节点,则将当前节点从链表中删除,即让当前节点的前一个节点prev指向当前节点的后一个节点。最后,如果遍历完整个链表,仍然没有找到值为x的节点,则输出“没有找到该节点”。
算法实现:
```
void deleteNode(CircularLinkedList &list, int x) {
ListNode *prev = list.head; // 前一个结点指针
ListNode *curr = prev->next; // 当前结点指针
while (curr != list.head) { // 遍历链表
if (curr->val == x) { // 如果找到了值为x的结点
prev->next = curr->next; // 删除当前结点
delete curr;
return;
}
prev = curr; // 更新指针
curr = curr->next;
}
// 如果遍历完整个链表仍然没有找到值为x的结点,则输出提示信息
cout << "没有找到该结点" << endl;
}
```
算法分析:
时间复杂度:O(n),其中n是链表的长度。最坏情况下,需要遍历整个链表才能找到值为x的节点。
空间复杂度:O(1),只需要维护两个指针prev和curr。
阅读全文