C++ 环形双向链表删除操作 - 代码实现 - 常规

C++ 环形双向链表删除操作 - 代码实现

问题描述： 构造一个环形双向链表，节点中存储的值为正整数，用这个链表进行删除操作。链表中的元素均不超过 100000。

输入格式： 多行输入，从第一行开始，每行一个正整数代表链表中的元素，直到遇到 -1，之后每行一个正整数 x，代表要删除的元素。若删除的元素在链表中存在，则将链表中所有的 x 全部删去，若不存在，则输出 -1。输入再次遇到 -1 结束，最后将链表中剩余的元素输出。

输出格式： 输出若干行，每行若干个整数。对于每个要删除的元素，若删除失败，输出 -1，最后输出链表的剩余元素。

C++ 代码：

#include <iostream>

using namespace std;

struct Node {
    int val;
    Node* prev;
    Node* next;
};

Node* createNode(int val) {
    Node* newNode = new Node;
    newNode->val = val;
    newNode->prev = nullptr;
    newNode->next = nullptr;
    return newNode;
}

void insertNode(Node** head, int val) {
    Node* newNode = createNode(val);
    if (*head == nullptr) {
        *head = newNode;
        newNode->next = newNode;
        newNode->prev = newNode;
    } else {
        Node* last = (*head)->prev;
        newNode->next = *head;
        newNode->prev = last;
        (*head)->prev = newNode;
        last->next = newNode;
    }
}

bool deleteNode(Node** head, int val) {
    if (*head == nullptr) {
        return false;
    }
    bool found = false;
    Node* current = *head;
    do {
        if (current->val == val) {
            found = true;
            if (current == *head && current->next == current) {
                *head = nullptr;
            } else {
                current->prev->next = current->next;
                current->next->prev = current->prev;
                if (*head == current) {
                    *head = current->next;
                }
            }
            delete current;
            current = current->next; // 继续检查下一个节点，因为可能有重复的元素
        } else {
            current = current->next;
        }
    } while (current != *head);
    return found;
}

void printList(Node* head) {
    if (head == nullptr) {
        return;
    }
    Node* current = head;
    do {
        cout << current->val << ' ';
        current = current->next;
    } while (current != head);
    cout << endl;
}

int main() {
    Node* head = nullptr;
    int val;
    cin >> val;
    while (val != -1) {
        insertNode(&head, val);
        cin >> val;
    }
    cin >> val;
    while (val != -1) {
        if (deleteNode(&head, val)) {
            printList(head);
        } else {
            cout << '-1' << endl;
        }
        cin >> val;
    }
    printList(head);
    return 0;
}

代码解释：

**结构体 Node：**定义节点结构，包含 val（节点值）、prev（前驱指针）、next（后继指针）。
**createNode 函数：**用于创建一个新的节点，初始化节点的值、前驱指针和后继指针。
**insertNode 函数：**用于将一个新的节点插入环形双向链表中。
- 如果链表为空，则新节点成为链表的头节点，并指向自身作为前驱和后继。
- 否则，将新节点插入链表末尾，并更新相关指针。
**deleteNode 函数：**用于从环形双向链表中删除指定值的节点。
- 如果链表为空，则返回 false，表示删除失败。
- 遍历链表，找到值为 val 的节点，进行删除操作。
  - 如果删除的是头节点且链表只有一个节点，则将 head 指针设置为 nullptr。
  - 否则，更新前驱和后继节点的指针，并删除当前节点。
- 如果找到并删除了节点，则返回 true，否则返回 false。
**printList 函数：**用于打印环形双向链表的元素，从头节点开始，遍历整个链表，直到回到头节点。
**main 函数：**主函数，用于输入元素构建链表，然后根据输入的要删除的元素进行操作，最后输出剩余的元素。

示例输入：

示例输出：