/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    if(!head||!head->next){return head;}
    struct ListNode *pre=head,*cur=head->next,*nxt;
    head->next=NULL;
    while(cur->next){
        nxt=cur->next;
        cur->next=pre;pre=cur;cur=nxt;
    }
    cur->next=pre;
    return cur;
}
bool cmpList(struct ListNode* a,struct ListNode* b){
    while(a&&b){
        if(a->val!=b->val) return false;
        a=a->next;b=b->next;
    }
    return true;
}
bool isPalindrome(struct ListNode* head) {
    struct ListNode *fast=head,*slow=head;
    while(fast&&slow&&fast->next){
        fast=fast->next->next;
        slow=slow->next;
    }
    if(fast&&slow){//奇数个
         fast=reverseList(slow->next);
    }else if(slow){//偶数
        fast=reverseList(slow);
    }
    return cmpList(head,fast);
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据