链接

代码：

class Solution {
public:bool isPalindrome(ListNode* head) {ListNode* slow = head;ListNode* fast = head;// while(slow&&fast){//     slow = slow->next;//     fast = fast->next;//     if(fast)//     {//         fast = fast->next;//     }        // }while(fast&&fast->next){fast = fast->next->next;slow = slow->next;}slow =  reverse(slow);fast = head;while(fast&&slow){if(fast->val!=slow->val){return false;}slow = slow->next;fast = fast->next;}return true;}ListNode* reverse(ListNode*head){ListNode*cur = head;ListNode* prev = nullptr;while(cur){ListNode*k = cur->next;cur->next = prev;prev = cur;cur = k;}return prev;}
};

 我的代码有个缺点：改变了原来的链表，即：将后二分之n长度反转了，如果有需要也可以再reverse回来，届时就不能直接return false，而使用一个flag，break出来，恢复原状之后再return；

其中的reverse方法两次写错：
第一次写错：

    // ListNode* reverse(ListNode*head){//     ListNode*cur = head;//     ListNode* res = nullptr;//     while(cur){//         head= cur->next;//         cur->next= head->next;//         head->next =cur;//     }//     return res;// }

第二次写错：

// ListNode* reverse(ListNode* root){//     if(!root){//         return nullptr;//     }//     ListNode*head = root;//     ListNode*p = root;//     ListNode*q = root->next;//     while(q){//         head->next = p->next;//         p->next = q->next;//         q->next = p;//     }//     return head;// }

 

---

还有一种方法，理解简单但是实现不简单，即：使得后half个节点反转，然后一个指针从头，一个指针从尾，比较half次，比较完之后，恢复原状。

class Solution {
public:bool isPalindrome(ListNode* head) {int len = 0;for(auto a = head;a;a = a->next)++len;if(len<=1) return true;int half = len/2;auto p = head;for(int i = 0;i<len-half;i++)p = p->next;auto q = p->next;for(int i = 0;i<half-1;i++){auto c = q->next;q->next = p;p = q;q = c;}auto tail = p;q = head;bool flag = true;for(int i = 0;i<half;i++){if(q->val!=p->val){flag = false;break;}q = q->next;p = p->next;}p = tail;auto k = tail->next;for(int i = 0;i<half-1;i++){auto c = k->next;k->next = tail;tail = k;k = c;}tail->next = nullptr;return flag;}
};