力扣[LeetCode].234. 迴文連結串列

第一步將後一半翻轉
第二步判斷是否對稱
第三步將後一半翻轉回來
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        int n=0;
        for(auto p=head;p;p=p->next) n++;
        if(n<=1) return true;
        int half=n/2;
        auto a=head;
        for(int i=0;i<n-half;i++) a=a->next;
        auto b=a->next;
        for(int i=0;i<half-1;i++){
            auto c=b->next;
            b->next=a;
            a=b,b=c;        
        }
    auto p=head,q=a;
    bool success=true;
    for(int i=0;i<half;i++){
        if(p->val != q->val){
            success=false;
            break;
        }
        p=p->next;
        q=q->next;
    }
    auto tail=a;
    b=a->next;
    //將連結串列恢復原狀
    for(int i=0;i<half-1;i++){
        auto c=b->next;
        b->next=a;
        a=b,b=c;
    }
    tail->next=NULL;
    return success;
    }
};