234.回文链表
思路1：双指针
1.一次遍历记录链表的值到数组中
2.数组头尾双指针开始判断
复杂度：
时间O(n),空间O(n)
代码：
class Solution {
public:bool isPalindrome(ListNode* head) {vector<int>nums;while(head){nums.push_back(head->val);head=head->next;}int i=0;int j=nums.size()-1;while(i<=j){if(nums[i]!=nums[j])return false;i++;j--;}return true;}
};
思路2:快慢指针+反转链表
1.快慢指针一次遍历到链表的中心
2.从中心开始反转链表后半部分
3.判断两段链表是否回文
复杂度：
时间O(n),空间O(1)
代码：
class Solution {
public:bool isPalindrome(ListNode* head) {ListNode* fast=head;ListNode* slow=head;while(fast->next!=nullptr&&fast->next->next!=nullptr){fast=fast->next->next;slow=slow->next;}//此时slow是前半段列表的末尾ListNode* backHead=reverse(slow->next);while(backHead!=nullptr){if(backHead->val!=head->val)return false;head=head->next;backHead=backHead->next;}return true;}ListNode* reverse(ListNode* head){ListNode* pre=nullptr;ListNode* cur=head;while(cur){ListNode* tmp=cur->next;cur->next=pre;pre=cur;cur=tmp;}return pre;}
};
