面试题：C++ 中循环链表的节点插入实现

Question

请使用C++ 实现一个循环链表，并编写一个函数，实现在指定节点后插入新节点的功能。要求给出完整的代码实现，包括循环链表的节点定义、插入函数以及简单的测试代码。

Answer 1

#include <iostream>

// 定义循环链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 在指定节点后插入新节点
void insertAfter(ListNode* prevNode, int newVal) {
    if (prevNode == nullptr) {
        return;
    }
    ListNode* newNode = new ListNode(newVal);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

// 简单的测试代码
int main() {
    // 创建循环链表: 1 -> 2 -> 3 -> 1
    ListNode* head = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    head->next = node2;
    node2->next = node3;
    node3->next = head;

    // 在节点2后插入新节点4
    insertAfter(node2, 4);

    // 遍历循环链表并输出节点值
    ListNode* current = head;
    do {
        std::cout << current->val << " ";
        current = current->next;
    } while (current != head);
    std::cout << std::endl;

    // 释放内存
    ListNode* temp;
    current = head;
    do {
        temp = current;
        current = current->next;
        delete temp;
    } while (current != head);

    return 0;
}