单链表判定回文

方法一 (后序递归+全局left指针，递归内right指针) ，时间复杂度O(n)，空间复杂度O(n)

利用后序递归+全局left指针，递归里面只要判断right是否==left。（left与right无法判断相对位置关系）

class Solution {
public:
    ListNode * p;
    bool helper(ListNode*root){
        if(root==nullptr){
            return true;
        }
        bool b=helper(root->next);
        if(b==true&&root->val==p->val){
            p=p->next;
            return true;
        }
        return false;
    }
    bool isPalindrome(ListNode* head) {
        if(head==nullptr){
            return true;
        }
        p=head;
        return helper(head);
    }
};

方法二 （快慢指针+翻转）， O(n)时间复杂度 O()

通过快慢指针得到中间点，从需要匹配的右侧串翻转，然后逐个匹配。

1->2->3->4 => 1->2-> | 3<-4

class Solution {
public:
    ListNode* helper(ListNode*&head){
        // 翻转
        if(head->next==nullptr){
            return head; 
        }
        ListNode* root = helper(head->next);
        head->next->next=head;
        head->next=nullptr;
        return root;
    }
    bool isPalindrome(ListNode* head) {
        if(head==nullptr){
            return true;
        }
        ListNode* pre=head;
        ListNode* next=head;
        int counts=0;
        while(next->next!=nullptr && next->next->next!=nullptr){
            pre=pre->next;
            next=next->next->next;
            counts++;
            // 0-(1)-(2)
            // 0-(1)-(2)-3
            // 0-1-(2)-3-(4)
        }
        if(next->next==nullptr){
            // odd
        }
        else{
            // even
            counts++;
            pre=pre->next;
        }
        ListNode* rev=helper(pre);
        for(int i=0;i<counts;i++){
            if(rev->val!=head->val){
                return false;
            }
            rev=rev->next;
            head=head->next;
        }
        return true;
    }
};