设计一个算法用于判断带头结点的循环列表是否对称并给出代码
时间: 2024-05-21 11:11:36 浏览: 37
建立带有头结点的链表
4星 · 用户满意度95%
好的,关于您的问题,以下是算法和代码:
算法:
1. 首先,需要找到循环列表的中间节点,使用快慢指针的方法可以实现,快指针每次移动2步,慢指针每次移动1步,当快指针到达列表尾部时,慢指针就指向了中间节点。
2. 然后,将节点从中间往后的所有节点反转,例如原来的顺序是1 -> 2 -> 3 -> 4 -> 5 -> 1,反转后的顺序就是1 -> 5 -> 4 -> 3 -> 2 -> 1。
3. 最后,从头结点开始和反转后的节点依次比较,如果值不相等,则说明不是对称的。
代码:
bool isSymmetric(Node* head) {
if (head == nullptr || head->next == nullptr) {
return true;
}
Node *slow = head->next, *fast = head->next;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
Node *pre = nullptr, *cur = slow->next, *next;
slow->next = nullptr;
while (cur != nullptr) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
while (head->next != nullptr && pre != nullptr) {
if (head->next->val != pre->val) {
return false;
}
head = head->next;
pre = pre->next;
}
return true;
}
注意:此代码适用于带头结点的循环列表,检查是否是对称的时,需要从 head->next 开始检查。
阅读全文