题解 | #链表的回文结构#

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/


/*
思路：将链表的节点逆置，然后得到的新链表与原链表进行比较，看是否相等，相等的话那么这个链表就具有回文结构
*/

/*
思路一：创建新的数组，遍历原链表，将链表节点中的值放入数组中，在数组中判断是否为回文结构

*/


class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        int arr[900]={0};
        ListNode *pcur=A;
        int i=0;
        while(pcur)//遍历原链表，pcur不能为空
        {
            //将链表中每个节点的值放到arr中
            arr[i]=pcur->val;
            i++;
            pcur=pcur->next;//换下一个节点
        }
        //i即节点的个数，因为我们的i一直在进行++操作

        //找中间节点，判断是否为回文数字
        int left=0;
        int right=i-1;//i是数组中数据的有效个数
        //我们比较left和right的下标的数字的大小，相等的话我们就让两个指针一直走，直到遍历整个数组
        while(left<right)
        {
            if(arr[left]!=arr[right])
            {
                //那么肯定不是回文结构
                return false;
            }
            right--;
            left++;

        }
        //说明是回文结构，因为已经跳出循环了
        return true;
    }
};