234

思路一：利用双指针技巧找到链表中点，将后半段链表反转，然后与前半段链表比较。这些技巧也是之前我们用到过的。

class Solution {
public:bool isPalindrome(ListNode* head) {ListNode *head1 = mid(head);head1 = head1->next;ListNode *head2 = reverse(head1);return string(head,head2);}//比较链个链表数值bool string(ListNode* p,ListNode* q){while(q){if(p->val == q->val){p = p->next;q = q->next;}elsereturn false;}return true;}//查找链比中点ListNode* mid(ListNode* head){ListNode *p = new ListNode(),*q = p;p->next = head;q->next = head;while(q&&q->next){p = p->next;q = q->next->next;}return p;}//反转链表ListNode* reverse(ListNode * head){ListNode *p = head;ListNode *q = nullptr;while(p!=nullptr){ListNode *tmp = p->next;p->next = q;q = p;p = tmp;}return q;}
};

思路二：利用栈的先进后出，将链表都入栈，然后一个一个出栈并与原链表进行比较，缺点是空间和时间复杂度比较大。

class Solution {
public:bool isPalindrome(ListNode* head) {stack <ListNode*> st;ListNode *p = head;//入栈while(p){st.push(p);p = p->next;}//出栈并比较while(head){ListNode *q = st.top();st.pop();if(q->val != head->val)return false;head = head->next;}return true;}};