首页 > 代码库 > 链表的回文结构

链表的回文结构


/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        ListNode *cur = A;
        ListNode *tmp = cur;
        ListNode *fast = A;
        ListNode *slow = A;
        ListNode *newHead=NULL;
        int count = 0;
        if(cur==NULL || cur->next==NULL)
            return true;
       while(fast&& fast->next!=NULL){
          
           fast=fast->next->next;
           slow=slow->next;
       }
        if(fast!=NULL && fast->next==NULL){
            count = 1;
        }
            
       cur=A;
        
       while(cur!=slow){
            tmp=cur;
           cur=cur->next;
            tmp->next =newHead;
           newHead=tmp;
           
        }
        if(count==1){
            slow = slow->next;
        }
        fast=newHead;
        while(slow!=NULL){
            if(fast->val==slow->val){
                fast=fast->next;
                slow=slow->next;
            }
            else{
                break;
            }         
        }
        if(slow==NULL)
            return true;
        return false;
      
    }
};


链表的回文结构