链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

我们来分析该题：我们首先要清楚什么是回文结构？其实就是对称结构。如果一个链表呈对称结构就说明该链表具有回文结构。 下面给上一些例子：

那我们怎么判断该链表是否属于回文结构呢？

思路1：将链表元素放到数组中，然后定义两个指针分别从头部和尾部开始遍历，如果对应位置上的元素相等就说明该链表属于回文结构。这个思路虽然可以解决问题，但是题目给出了空间复杂度为O(1)的限制，所以该方法不可行。

思路2： 我们首先找到链表的中间节点，然后将中间节点之后的链表逆置，然后分别从第一个节点和逆置后的中间节点开始比较，如果对应位置上的元素相同则说明该链表符合回文结构，否则不符合。

画图表示：

有了思路，我们只需要完成第一步和第二步。找到中间节点以及逆置链表。 

找链表的中间节点我在前面已经解答过了我们在这里直接CV即可。没了解过的可以看这篇博客——leetcode——链表的中间节点-CSDN博客。

逆置链表我在前面也已经解答过了我们依旧CV一下。不了解的可以看这篇——leetcode——反转链表-CSDN博客。

我们对思路进行了分析也完成了准备工作，现在我们来实现该题目：

class PalindromeList {
public:

    //逆置链表方法
    ListNode* reverseList(ListNode* head)
    {
        //如果原链表为空，直接返回NULL
        if(head == NULL)
        {
            return NULL;
        }

        //原链表不为空
        ListNode*n1 = NULL;
        ListNode*n2 = head;
        ListNode*n3 = head->next;
        while(n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if(n3!=NULL)
            {
                n3 = n3->next;
            }
        }
        return n1;
    }

    //寻找中间节点方法
    ListNode* middleNode(ListNode* head) 
    {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    bool chkPalindrome(ListNode* A) 
    {
        ListNode* mid = middleNode(A);
        ListNode* rev = reverseList(mid);
        ListNode*pcur = A;
        while(pcur && rev)
        {  
            if(pcur->val != rev->val)
            {
                return false;
            }
            pcur = pcur->next;
            rev = rev->next;
        }
        return true;
    }
};