算法设计题:设计一个程序用于判断带头结点的循环双链表是否对称。写出功能完全的代码
时间: 2024-09-28 21:08:59 浏览: 3
要判断一个带头结点的循环双链表是否对称,你可以使用两个指针,一个从头节点开始正向遍历,另一个从尾节点的前驱节点(也就是倒数第二个节点)开始反向遍历。如果这两个指针指向的节点相等并且它们各自还有对应的下一个节点,那么继续移动;否则,列表就不是对称的。
以下是一个 C++ 实现的例子:
```cpp
#include <iostream>
// 定义链表节点结构
struct Node {
int data;
Node* next;
Node* prev;
};
// 判断链表是否对称
bool isSymmetric(Node* head) {
if (head == nullptr || head->next == nullptr) {
return true; // 空链表或只有一个元素都是对称的
}
Node* slow = head;
Node* fast = head->prev->prev;
while (fast != nullptr && fast->next != nullptr) {
if (slow != fast) {
return false; // 如果某一对节点不相等,链表不对称
}
slow = slow->next;
fast = fast->next->next;
}
return true; // 遍历结束,没有发现不相等的节点,链表是对称的
}
int main() {
// 这里省略了链表的具体创建和初始化步骤
// 假设你已经有了一个带头结点的循环双链表
Node* head = ...;
// 调用函数检查并打印结果
if (isSymmetric(head)) {
std::cout << "The linked list is symmetric.\n";
} else {
std::cout << "The linked list is not symmetric.\n";
}
return 0;
}
```