题解 | #判断一个链表是否为回文结构#

数组法

这里将链表存到数组中后设置了头尾两个标记，分别从首尾开始进行判断是否相等

bool isPail(ListNode* head) {
        // write code here
        //因为链表没有办法逆序遍历所以给他存到数组中就可以了
        vector<int> nums;
        while(head){
            nums.push_back(head->val);
            head=head->next;
        }
        int left=0;
        int right=nums.size()-1;
        //回文字符串判断一半就可以了
        while(left<=right){
            if(nums[left]!=nums[right])
                return false;
            left++;
            right--;
        }
        return true;
    }

双指针法（推荐）

这里用到了反转链表

//反转链表
    ListNode* reverse(ListNode *head){
        ListNode *pre=nullptr;
        ListNode *cur=head;
        ListNode *nex=nullptr;
        while(cur){
            nex=cur->next;//保存下一个位置
            cur->next=pre;//指向反转
            pre=cur;
            cur=nex;
        }
        return pre;
    }
    bool isPail(ListNode *head) {
        // write code here
        if(head==nullptr)
            return true;
        ListNode *fast=head;
        ListNode *slow=head;
        //双指针确定中点
        while(fast && fast->next){
            fast=fast->next->next;
            slow=slow->next;
        }
        //中点处反转
        slow =reverse(slow);
        fast=head;
        //比较节点是否相当
        while(slow){
            if(slow->val!=fast->val)
                return false;
            fast=fast->next;
            slow=slow->next;
        }
        return true;
    }