题目描述

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1

返回：true

考察基本的链表操作，两种方法：

1.将链表转化为数组进行处理。

2.将链表反转再进行比较。

1

/*struct ListNode {    int val;    struct ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};*/class PalindromeList {public:    bool chkPalindrome(ListNode* A) {        // write code here        vector
    
      res;        bool flag=true;        while(A){            res.push_back(A->val);            A=A->next;        }        for(int i=0;i
    

2. 要注意理解反转的操作

/*struct ListNode {    int val;    struct ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};*/class PalindromeList {public:    bool chkPalindrome(ListNode* A) {        // write code here        if(A==NULL)            return false;        else if(A->next==NULL)            return true;        //快慢指针找出中间节点        ListNode* quick=A;        ListNode* slow=A;        while(quick!=NULL&&quick->next!=NULL)        {            quick=quick->next->next;            slow=slow->next;        }        //反转        ListNode* p=slow->next;        ListNode* p1=p->next;               while(p!=NULL)        {            p->next=slow;            slow=p;            p=p1;            p1=p1->next;        }                 while(A!=slow)        {            if((A->val)!=(slow->val))            {                return false;            }else{                if(A->next==slow)                {                    return true;                }                A=A->next;                slow=slow->next;            }        }        return true;             }};