判断一个链表是否是回文结构

方法一：（数组反转法）

思路：

1.创建一个数组，用于存链表中的每个节点的值

2.再创建一个数组，复制前一个数组的值，再进行反转

3.比较两个数组，判断是否是回文结构

代码：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    bool isPail(ListNode* head) {
        //将链表中的节点拿下来放在容器nums中
       vector<int> nums;
       while(head!=NULL){
           nums.push_back(head->val);
           head=head->next;
       }
       //创建一个新的容器temp，先复制nums的内容，再用reverse函数进行反转
       //reverse(temp.begin(),temp.end());
       vector<int> temp;
       temp=nums;
       reverse(temp.begin(),temp.end());
       //再进行一一对比两个数组，如果遇到不一样的那么就表示不是回文
       for(int i=0;i<temp.size()-1;i++){
            if(temp[i]!=nums[i]){
                return false;
            }
       }
       return true;
    }
};

方法二：数组+对撞指针

思路：

1.先将链表中的节点的值放入到数组中

2.再设置两个指针，分别位于数组的两个端点

3.左指针右移动，右指针左移，直到两者相撞，判断两个对应的值是否相同

代码：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    bool isPail(ListNode* head) {
        //将链表的节点拿下来存在容器中
        vector<int> nums;
        while(head!=NULL){
            nums.push_back(head->val);
            head=head->next;
        }
        //设置两个对撞指针，分别从数组的两个端点进行同向的移动
        //只要两个指针还没有相撞，那么就进行比较，如果不同，那么就表示不是回文结构，否则就是回文结构
        int left=0,right=nums.size()-1;
        while(left<=right){
            if(nums[left]!=nums[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};