【初阶数据结构】——牛客：OR36 链表的回文结构

1. 题目介绍

链接: link

这道题呢是让我们判断一个链表是否是回文结构。但是题目要求设计一个时间复杂度为O(n)，额外空间复杂度为O(1)的算法。 所以如果我们想把链表的值存到一个数组中再去判断就不可行了。

2. 思路分析

那对于这道题呢比较好的一个思路是这样的：

不是要判断链表是否是回文结构嘛。 回文结构的话就是从中间分开，两边是对称的嘛（比如：1，2 | 2，1），当然如果是奇数个结点的话就是以中间结点为对称轴（比如：1 2 3 2 1）。 那我就可以这样做： 找到链表的中间结点，将从中间结点开始往后的部分进行逆置（如果是偶数个有两个中间结点就从第二个开始）。 后半部分逆置之后，我们比较这两部分是否相同，如果相同，他就是回文结构。

单凭上面的文字大家可能还不是特别清楚，下面我们来画个图分析一下：

就以1 2 2 1为例：

首先找到中间结点是2（第二个2），这里找链表中间结点我们前面就做过这个题，到时候就可以直接用。 那逆置之后就是这样

链表逆置之前我们也写过对应的OJ题，待会也可以直接用。那逆置之后我们可以拿到逆置之后后半部分链表的头指针。 同时题目给了我们原链表的头指针。

那然后我们就可以同时从这两个头指针开始往后遍历，依次两个比较每对结点，如果某次比较不相同，那就不是回文结构，直接返回false。 如果是回文结构，就一直向后比，所以肯定要写成循环，那循环什么时候结束呢？ 🆗，后半部分链表逆置之后最后一个结点指向空，所以如果遍历到rhead为空，还没返回false，那就是全部相同，他就是回文结构，此时循环结束，返回true。

但是上面我们分析的是偶数个结点的情况，如果是奇数个，还适用吗？

🆗，是可以的。 以1 2 3 2 1为例

逆置后半部分之后是这样子。 然后还是两两比较，1 2相等，2 2 相等

此时我们看到对于前半部分链表来说，到2就遍历完了。后半部分虽然每遍历完，但是奇数个的话，他最后剩下的那个就是原链表最中间的那个结点。 那中间结点的左右两部分都相等了，其实已经证明是回文了，就可以结束了。 所以逆置之后是不是应该把前半部分的尾结点next置空，这样只要有一个链表走到空就结束，就是回文。 可以置空，但是其实没必要。而且要置空的话还得保存一下中间结点的前一个，怪麻烦的。

我们看到，不置空的话，此时前半部分的尾结点（这里是2）指向谁？ 就是原链表的中间结点，所以可以继续向后比较，自己跟自己比，肯定相同，那再往后后半部分链表就走到空了。循环结束，返回true。 如果不是回文链表，中间比较的时候不相同就直接返回false了。 所以不需要将前半部分尾结点next置空，循环结束的条件就是后半部分链表走到空。

3. 代码实现

那我们来写一下代码：

这两个函数我就直接拷贝之前我们写过的代码了，之前的文章我们都讲过，大家可以去看。

就搞定辽！

提交一下：

过啦！

class PalindromeList {
  public:
    struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* newhead = NULL;
        struct ListNode* cur = head;
        struct ListNode* tmp = NULL;
        while (cur) {
            //保存下一个的地址
            tmp = cur->next;
            //头插
            cur->next = newhead;
            newhead = cur;
            cur = tmp;
        }
        return newhead;
    }

    struct ListNode* middleNode(struct ListNode* head) {
        struct ListNode* slow = head;
        struct ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    bool chkPalindrome(struct ListNode* A) {
        struct ListNode* midnode=middleNode(A);
        struct ListNode* rhead=reverseList(midnode);
        while(rhead)
        {
            if(A->val!=rhead->val)
                return false;
            A=A->next;
            rhead=rhead->next;
        }
        return true;
    }
};