已知一个带头结点的循环链表为list，设计一个算法，删除链表中数据域值为item的所有节点。
引用 皆我百晓生 小程序回复内容作答：
下面是C++中一个删除循环链表中数据域值为item的所有节点的算法示例：
#include <iostream>
// 定义循环链表节点结构
struct Node {
int data;
Node* next;
};
// 创建循环链表
Node* createCircularLinkedList(int arr[], int size) {
Node* head = new Node;
head->next = nullptr;
Node* tail = head;
for (int i = 0; i < size; i++) {
Node* newNode = new Node;
newNode->data = arr[i];
newNode->next = nullptr;
tail->next = newNode;
tail = newNode;
}
tail->next = head; // 将最后一个节点的next指向头结点
return head;
}
// 删除循环链表中数据域值为item的所有节点
void deleteNodes(Node* head, int item) {
Node* current = head->next;
Node* previous = head;
while (current != head) {
if (current->data == item) {
Node* temp = current;
previous->next = current->next;
current = current->next;
delete temp;
} else {
previous = current;
current = current->next;
}
}
}
// 打印循环链表
void printCircularLinkedList(Node* head) {
Node* current = head->next;
while (current != head) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
int main() {
int arr[] = {1, 2, 3, 2, 4, 2, 5};
int size = sizeof(arr) / sizeof(arr[0]);
Node* head = createCircularLinkedList(arr, size);
std::cout << "原始链表: ";
printCircularLinkedList(head);
int item = 2;
deleteNodes(head, item);
std::cout << "删除数据域为" << item << "的节点后: ";
printCircularLinkedList(head);
return 0;
}
这是一个示例程序，它首先创建了一个循环链表，然后使用deleteNodes函数删除数据域值为item的所有节点。最后，使用printCircularLinkedList函数打印删除节点后的链表。
注意，这里假设循环链表是带有头结点的，头结点的数据域可以为空或填充任意值。在deleteNodes函数中，我们使用了两个指针previous和current来遍历链表，查找并删除数据域值为item的节点。删除节点时，我们将前一个节点的next指针指向当前节点的下一个节点，并释放删除节点的内存。
希望这个算法能够帮助你解决问题。如果你有任何疑问，请随时提问。
【以下回答由 GPT 生成】
def delete_nodes(list, item):
if list.next is None: # 判断链表是否为空
return list
current = list.next # 从头结点的下一个节点开始遍历
prev = list # 记录当前节点的前一个节点
while current != list: # 遍历整个链表
if current.data == item: # 如果当前节点的数据域等于待删除的item值
prev.next = current.next # 删除当前节点
current = current.next # 继续向后遍历
else:
prev = current # 更新prev指向当前节点
current = current.next # 继续向后遍历
# 删除头结点中数据域值为item的节点
if list.data == item:
prev.next = list.next
list = prev.next
return list
解释:
current指向链表的第一个非头结点，prev初始化为头结点。next指向当前节点的下一个节点，即删除当前节点。prev指针为当前节点，并更新current指针为当前节点的下一个节点。算法的时间复杂度为O(n)，其中n为链表中节点的个数。
【相关推荐】