题解 | #链表的回文结构#
链表的回文结构
https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; */ class PalindromeList { public: // 检查链表是否为回文 bool chkPalindrome(ListNode* A) { // 如果链表为空,直接返回 false if (A == NULL) return false; // 使用快慢指针找到链表的中间节点 ListNode* slow = A, *fast = A; while (fast && fast->next) { slow = slow->next; // 慢指针每次移动一步 fast = fast->next->next; // 快指针每次移动两步 } // 反转链表的后半部分 ListNode* cur = NULL, *next = slow; while (slow) { next = slow->next; // 暂存下一个节点 slow->next = cur; // 将当前节点的 next 指向前一个节点,完成反转 cur = slow; // 更新前一个节点为当前节点 slow = next; // 将当前节点移动到下一个节点 } // 将next指针重新指向链表的头部,用于从头开始比较 next = A; // 比较前半部分和反转后的后半部分的节点值 while (cur) { if (next->val != cur->val) // 若节点值不相同,说明不是回文 return false; next = next->next; // 移动到下一个节点 cur = cur->next; // 反转部分也移动到下一个节点 } // 若所有节点值都匹配,则链表为回文,返回 true return true; } };