【题目】
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
进阶：你能否用?O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
【题解】
class Solution
{
public:
bool isPalindrome(ListNode* head)
{
//问题可以分为四步
//找到前半段的最后一个结点，把链表一分为二
//翻转后半段的链表
//对比翻转后的后半段与前半段是否完全一样
//恢复后半段链表
if(head==nullptr)
{
return true;
}
ListNode* half_node=find_half_node(head);
ListNode* reverse_half_node=reverseList(half_node->next);
ListNode* p1 = head;
ListNode* p2 = reverse_half_node;
bool result = true;
while (result && p2 != nullptr &&p1!=nullptr)
{
if (p1->val != p2->val)
{
result = false;
}
p1 = p1->next;
p2 = p2->next;
}
half_node->next = reverseList(reverse_half_node);
return result;
}
private:
//用于寻找前半段最后一个结点
ListNode* find_half_node(ListNode* head)
{
ListNode* fast=head;
ListNode* slow=head;
if(fast->next!=nullptr&&fast->next->next!=nullptr)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
//用于翻转链表
ListNode* reverseList(ListNode* head)
{
ListNode* pre_node=nullptr;
ListNode* cur_node=head;
while(cur_node!=nullptr)
{
ListNode* next_node=cur_node->next;
cur_node->next=pre_node;
pre_node=cur_node;
cur_node=next_node;
}
return pre_node;
}
};
