日野弥生：勉強しよう
LeetCode 234 - 回文链表
发表于2025年01月22日
本题要求仅用O(n)的时间复杂度和O(1)的空间复杂度，但是不要求链表结构不发生改变。所以可以考虑通过修改链表结构来造成节省时间复杂度的局面。
解题方法：双指针法
快指针比慢指针每次多走一步，快指针到终点时，慢指针指向中间位置。而且慢指针在迭代过程中，不断地翻转前半段链表，从而快指针到达终点时，原始链表分为了两条。
同时，巧妙地利用慢指针在迭代过程中记录的前指针，利用慢指针和慢指针的前指针构成一堆新的双指针，进行两个新链表的迭代，检查每一步内双指针的数值是否相同，进而判断出是否回文。
class Solution {
public:
bool isPalindrome(ListNode* head) {
/* 由于快指针每次走两步，需要检查边界情况 */
if(!head || !head->next)
return true;
ListNode *slow = head, *fast = head, *slowPrev = nullptr;
/* 快指针到终点时，慢指针刚好到中间 */
while(fast && fast->next)
{
fast = fast->next->next;
/* 慢指针在移动过程中，同时把链表反转 */
ListNode *slowNext = slow->next;
slow->next = slowPrev;
slowPrev = slow;
slow = slowNext;
}
bool result = true;
/* 偶数情况 */
if(!fast)
{
while(slow)
{
if(slow->val != slowPrev->val)
{
result = false;
break;
}
slow = slow->next;
slowPrev = slowPrev->next;
}
}
/* 奇数情况 */
else if(!fast->next)
{
slow = slow->next;
while(slow)
{
if(slow->val != slowPrev->val)
{
result = false;
break;
}
slow = slow->next;
slowPrev = slowPrev->next;
}
}
return result;
}
};