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

题目的主要信息：

• 给定一个链表的头节点，判读该链表是否为回文结构
• 回文结构即正序遍历与逆序遍历结果都是一样的，类似123321
• 空链表默认为回文结构

方法一：数组复制反转法

具体做法：

即然回文结构正序遍历和逆序遍历结果都是一样的，我们是不是可以尝试将正序遍历的结果与逆序遍历的结果一一比较，如果都是对应的，那很巧了！它就是回文结构！

这道题看起来解决得如此之快，但是别高兴太早，链表可没有办法逆序遍历啊。链表由前一个节点的指针指向后一个节点，指针是单向的，只能从前面到后面，我们不能任意访问，也不能从后往前。但是，另一个容器数组，可以任意访问，我们把链表中的元素值取出来放入数组中，然后判断数组是不是回文结构，这不是一样的吗？

逆序遍历，不就是将数组反转之后的再遍历吗？那我们准备另一个辅助数组，接受反转后的结果，两个数组同时同步从左往右遍历，第一个数组就是正序，第二个数组就是逆序，如果是回文结构，那么两种遍历每一步遇到的元素都应该是相同的，只要遇到一个不同的，就不会回文结构。

class Solution {
public:
    bool isPail(ListNode* head) {
        vector<int> nums;
        while(head != NULL){ //将链表元素取出一次放入数组
            nums.push_back(head->val);
            head = head->next;
        }
        vector<int> temp = nums; 
        reverse(temp.begin(), temp.end()); //准备一个数组承接翻转之后的数组
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] != temp[i]) //正向遍历与反向遍历相同
                return false;
        }
        return true;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为链表的长度，遍历链表转化数组为$O(n)O(n)$，反转数组为$O(n)O(n)$，后续遍历两个数组为$O(n)O(n)$
• 空间复杂度：$O(n)O(n)$，记录链表元素的辅助数组

方法二：数组复制双指针

具体做法：

既然方法一我们已经将链表的值放入了数组中，数组是可以按照下标直接访问的，那干啥还要傻乎乎地用另一个数组来表示反转后的数组呢？我们直接从后往前遍历与从前往后遍历一同比较，不就少了很多额外的时间了吗？对于数组从后往前与从前往后一起比较，我们可以使用下标访问，两个下标代表两个指针，左指针指向开头，从左到右，右指针指向数组末尾，从右到左，依次比较二者经过的元素是不是一样的，如果有不一样的就结束。

那什么时候停下来呢？一定要左指针到了末尾，右指针到了开头吗？不需要！只要两个指针相遇就好了，因为左指针到了右半部分都是右指针走过的路，比较的值也是与之前相同的。

具体比较过程可以参考下图：

class Solution {
public:
    bool isPail(ListNode* head) {
        vector<int> nums;
        while(head != NULL){ //将链表元素取出一次放入数组
            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;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为链表的长度，遍历链表转化数组为$O(n)O(n)$，双指针遍历半个数组为$O(n)O(n)$
• 空间复杂度：$O(n)O(n)$，记录链表元素的辅助数组

方法三：栈逆序

具体做法：

同样的，逆序访问我们不一定需要借助可以随机访问的数组，我们还可以借助先进先出的栈：根据链表顺序入栈的元素，越在前面的就越在栈底，越在后面的就越在栈顶，因此后续从栈中弹出的元素，依次就是链表的逆序。

那我们可以依次从栈中弹出元素值，和链表的顺序遍历比较，如果都是一一比较相同的值，那正好就是回文，否则就不是。

class Solution {
public:
    bool isPail(ListNode* head) {
        ListNode* p = head;
        stack<int> s;
        while(p != NULL){ //辅助栈记录元素
            s.push(p->val);
            p = p->next;
        }
        p = head;
        while(!s.empty()){ //正序遍历链表，从栈中弹出的内容是逆序的
            if(p->val != s.top()) //比较是否相同
                return false;
            s.pop();
            p = p->next;
        }
        return true;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为链表的长度，遍历链表入栈为$O(n)O(n)$，后续再次遍历链表和栈
• 空间复杂度：$O(n)O(n)$，记录链表元素的辅助栈

方法四：长度法找中点

具体做法：

在数组中，我们可以借助双指针，一个从前往遍历前一半数组，另一个从后往前遍历后一半数组，依次比较值。链表中如果我们要用这样的思想，左指针从前往后很容易，直接的链表的遍历就可以了。但是右指针是真的没有办法从尾巴往前走，要是链表后半段的指针是逆序的就好了。

怎么样能让链表后半段的指针反过来，将后半段链表整体反转不就行了吗？如果我们将后半段链表整体反转，那么相当于后半段就是从末尾指向中间，就可以实现后半段的逆序遍历——按照指针直接走就可以了。

但是现在有一个问题，我们要怎么找到中间个节点，让我们可以精准地反转后半段呢？最简单的方式，莫过于遍历链表所有的节点，得到了总节点数，取1/2不就是一半的节点数吗？我们可以遍历这一半的数量，抵达中点，然后精准地从中点开始往后反转后半段链表就可以了。

比较正序与逆序的时候，和方法二类似，左指针指向链表开头，右指针指向链表尾，此时链表前半段是正常的，我们也可以正常遍历，但是链表后半段所有指针都被我们反转逆序，因此我们可以从尾节点往前遍历。依次比较对应位置的元素值即可。

具体过程可以参考如下图：

class Solution {
public:
    ListNode* reverse(ListNode* head) { //反转链表指针
        ListNode* prev = NULL; //前序节点
        while (head != NULL) {
            ListNode* next = head->next; //断开后序
            head->next = prev; //指向前序
            prev = head;
            head = next;
        }
        return prev;
    }
    bool isPail(ListNode* head) {
        ListNode* p = head;
        int n = 0;
        while(p != NULL){ //找到链表长度
            n++;
            p = p->next; 
        }
        n = n / 2; //中点
        p = head;
        while(n > 0){
            p = p->next;
            n--;
        }
        p = reverse(p);  //中点处反转
        ListNode* q = head;
        while (p != NULL) {
            if (p->val != q->val) //比较判断节点值是否相等
                return false;
            p = p->next;
            q = q->next;
        }
        return true;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为链表的长度，遍历链表找到长度为$O(n)O(n)$，后续反转链表为$O(n)O(n)$，然后再遍历两份半个链表
• 空间复杂度：$O(1)O(1)$，常数级变量，没有额外辅助空间

方法五：双指针找中点

具体做法：

上述方法四找中点，我们遍历整个链表找到长度，又遍历长度一半找中点位置。过程过于繁琐，我们想想能不能优化一下，一次性找到中点。

我们首先来看看中点的特征，一个链表的中点，距离链表开头是一半的长度，距离链表结尾也是一半的长度，那如果从链表首遍历到链表中点位置，另一个每次遍历两个节点的指针是不是就到了链表尾，那这时候我们的快慢双指针就登场了：

• step 1：慢指针每次走一个节点，快指针每次走两个节点，快指针到达链表尾的时候，慢指针刚好到了链表中点。
• step 2：从中点的位置，开始往后将后半段链表反转。
• step 3：按照方法四的思路，左右双指针，左指针从链表头往后遍历，右指针从链表尾往反转后的前遍历，依次比较遇到的值。

找中点的过程可以参考如下图示：（比较过程参考方法四的图）

class Solution {
public:
    ListNode* reverse(ListNode* head) { //反转链表指针
        ListNode* prev = NULL; //前序节点
        while (head != NULL) {
            ListNode* next = head->next; //断开后序
            head->next = prev; //指向前序
            prev = head;
            head = next;
        }
        return prev;
    }
    bool isPail(ListNode* head) {
        if(head == NULL) //空链表直接为回文
            return true;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != NULL && fast->next != NULL){ //双指针找中点
            slow = slow->next;
            fast = fast->next->next;
        }
        slow = reverse(slow);  //中点处反转
        fast = head;
        while (slow != NULL) { 
            if (slow->val != fast->val) //比较判断节点值是否相等
                return false;
            fast = fast->next;
            slow = slow->next;
        }
        return true;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为链表的长度，双指针找到中点遍历半个链表，后续反转链表为$O(n)O(n)$，然后再遍历两份半个链表
• 空间复杂度：$O(1)O(1)$，常数级变量，没有额外辅助空间