算法设计题:设计一个程序用于判断带头结点的循环双链表是否对称。写出功能完全的代码,补上创建和初始化
时间: 2024-09-28 16:09:02 浏览: 49
当我们需要判断一个带头结点的循环双链表是否对称时,我们可以使用两个指针,一个从头节点开始,另一个从尾节点开始,同时向前移动。如果在任何时候这两个指针指向的节点不相等,或者它们无法到达相同的节点,则链表不对称;否则,它是对称的。
以下是完整的C++代码,包括创建、初始化以及判断链表对称的功能:
```cpp
#include <iostream>
// 定义循环双链表节点结构
struct ListNode {
int data;
ListNode* prev;
ListNode* next;
};
// 创建一个新的循环双链表节点
ListNode* createNode(int value) {
ListNode* newNode = new ListNode();
if (newNode == nullptr) {
std::cerr << "Memory allocation failed." << std::endl;
return nullptr;
}
newNode->data = value;
newNode->prev = newNode;
newNode->next = newNode; // 带头结点的链接
return newNode;
}
// 初始化循环双链表
ListNode* initializeList(ListNode** head, const std::vector<int>& values) {
*head = createNode(values[0]); // 创建头节点
ListNode* current = *head;
for (size_t i = 1; i < values.size(); ++i) {
ListNode* newNode = createNode(values[i]);
if (newNode == nullptr) {
return nullptr; // 如果分配失败,返回nullptr
}
current->next = newNode;
newNode->prev = current;
current = newNode;
}
(*head)->next = *head; // 关闭环路
return *head;
}
// 检查链表是否对称
bool isSymmetric(ListNode* head) {
if (head == nullptr || head->next == head) {
return true; // 链表为空或只有一个元素,视为对称
}
ListNode* slow = head;
ListNode* fast = head->next;
while (fast != nullptr && fast->next != head) {
if (slow->data != fast->data) {
return false; // 数据不匹配,链表不对称
}
slow = slow->next;
fast = fast->next->next;
}
return true; // 快慢指针相遇,链表可能对称或已经检查过所有节点
}
int main() {
std::vector<int> values = {1, 2, 2, 1}; // 示例数据
ListNode* head = nullptr;
// 初始化链表
if (head = initializeList(&head, values)) {
bool symmetric = isSymmetric(head);
if (symmetric) {
std::cout << "The linked list is symmetric." << std::endl;
} else {
std::cout << "The linked list is not symmetric." << std::endl;
}
} else {
std::cerr << "Failed to initialize the list." << std::endl;
}
return 0;
}
```
阅读全文