educoder数据结构 循环链表的设计与实现单链表闯关答案

循环链表是一种特殊的链表结构，它的尾节点指向头节点，形成一个环形结构。与单链表相比，循环链表的插入和删除操作更为方便，因为不需要考虑头节点的特殊情况。

设计与实现循环链表的关键是定义节点类和循环链表类。节点类需要包含一个数据成员，用来保存节点数据，以及一个指针成员，用来指向下一个节点。循环链表类则需要包含头节点指针和链表长度等属性，以及插入、删除和打印链表等方法。

首先，定义节点类：

class ListNode {
public:
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

然后，定义循环链表类：

class CircularLinkedList {
private:
ListNode *head;
int count;
public:
CircularLinkedList() {
head = NULL;
count = 0;
}

// 在链表末尾插入节点
void insertAtEnd(int val) {
ListNode *newNode = new ListNode(val);
if (head == NULL) {
head = newNode;
head->next = head;
} else {
ListNode *temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
}
count++;
}

// 删除指定位置的节点
void deleteAt(int pos) {
if (pos < 1 || pos > count) {
cout << "位置不合法" << endl;
return;
}
ListNode *temp = head;
if (pos == 1) {
head = head->next;
delete temp;
} else {
for (int i = 1; i < pos - 1; i++) {
temp = temp->next;
}
ListNode *nodeToDelete = temp->next;
temp->next = temp->next->next;
delete nodeToDelete;
}
count--;
}

// 打印链表
void printLinkedList() {
if (head == NULL) {
cout << "链表为空" << endl;
return;
}
ListNode *temp = head;
do {
cout << temp->val << " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}
};

通过定义节点类和循环链表类，我们可以方便地进行循环链表的插入、删除和打印操作。在闯关过程中，我们可以根据题目要求，使用循环链表来解决相关问题。