想放弃吗？，那当初为什么要开始？
题目描述
给定一个链表的 头节点 head ，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
示例 1：
输入: head = [1,2,3,3,2,1]
输出: true
示例 2：
输入: head = [1,2]
输出: false
思路分析
-
如果使用容器来做，使用栈，先把元素都入栈，然后出栈和链表元素比较。
-
时间复杂度O(n),空间复杂度O(n).不是最优解
-
最优解：时间复杂度O(n),空间复杂度O(1),不使用额外变量，仅仅通过操作指针来完成
-
通过快慢指针找到中间节点
-
反转后半部分的链表
-
定义两个指针，依次判断，前半部分的链和后半部分的链是否相等
完整代码
class Solution {
public:
//反转链表
ListNode* Reverse(ListNode*head)
{
auto newhead=new ListNode(0,head);
auto p=head;
newhead->next=NULL;//要断开
while(p!=NULL)
{
auto q=p->next;
p->next=newhead->next;
newhead->next=p;
p=q;
}
return newhead->next;
}
//寻找中间节点
ListNode* findMiddle(ListNode*head)
{
auto fast=head;
auto slow=head;
//快指针要么走到最后一个节点，要么走到空，对应着奇数偶数个节点
while(fast!=NULL&&fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
//判断两个链表是否一致
bool Is_same(ListNode*l1,ListNode*l2)
{
while(l2&&l1)
{
if(l1->val!=l2->val)
return false;
l1=l1->next;
l2=l2->next;
}
return true;
}
bool isPalindrome(ListNode* head) {
if(head==NULL)
return true;
//最优解：
//1.找到中间节点
//2.反转中间节点往后的节点
//3.从第一个节点和中间节点往后遍历，看是否完全相等
ListNode* middle=findMiddle(head);
ListNode* l2=Reverse(middle);
return Is_same(head,l2);
}
};