设计一个算法判断带头节点的双向循环链表是否对称
时间: 2024-10-10 09:05:34 浏览: 20
设计一个算法来判断一个带头节点的双向循环链表是否对称,可以采用两个指针,分别从头节点开始向前和向后遍历,并比较它们指向的节点值是否相等。如果发现某个时刻两个指针指向的节点不相等,则链表不对称;如果都能遍历完整个链表而未发现不匹配的节点,那么链表是对称的。
以下是步骤描述:
1. 初始化两个指针,一个指向头节点,命名为`fast`,速度较快,每次前进两步;另一个指向下标为0的头节点,命名为`slow`,每次只前进一步。
2. 当`fast`指针遇到尾部的循环点(即`fast`为NULL但`fast->next->next`非NULL),同时`slow`指针还未到达头部的循环点时,进入循环。
3. 在循环中,每次都检查`slow`和`fast`所指节点的值是否相等。如果不等,直接返回`false`表示链表不对称。
4. 如果遍历过程中所有节点的值都相等,说明链表对称,返回`true`。
```cpp
// 假设head是链表的头节点
bool isSymmetric(DoublyListNode* head) {
if (head == nullptr || head->next == nullptr) {
return true;
}
DoublyListNode *slow = head, *fast = head->next->next;
while (slow != fast) {
if (slow == nullptr || fast == nullptr || slow->val != fast->val) {
return false;
}
slow = slow->next;
if (fast != nullptr) {
fast = fast->next->next;
}
}
return true;
}
```