题解 | #链表的回文结构#

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A)
    {
        //特殊情况的操作
        if(A==NULL||A->next==NULL)//如果是空链表或者是一个节点的链表的话，那么肯定是回文结构的
        {
            return true;
        }

        //使用快慢指针找到链表的中间节点，最后停下来的时候慢指针就在中间节点上面
        ListNode *slow=A;
        ListNode *fast=A;
        while(fast!=NULL&&fast->next!=NULL)
        {
            slow=slow->next;//慢指针移动一步
            fast=fast->next->next;//快指针移动两步
        }

        //2.反转链表的后半部分
        ListNode *prev=NULL;
        ListNode *cur=slow;//这个时候的slow在这个链表的中间节点，那么我们从中间节点反转后半部分
        while(cur!=NULL)//从当前位置进行遍历后半部分的链表
        {
            //下面就是链表反装的代码，将后半部分链表进行反装的操作
            ListNode *nexttmp=cur->next;//保存当前节点的下个节点

            //下面两个代码是当前节点和前一个节点的转换操作
            //当前节点的next指向我们的前一个节点
            cur->next=prev;//将当前节点的指针反装，指向前一个节点，
            prev=cur;//当前的节点变成了上一个节点了

            cur=nexttmp;//更换当前的节点继续进行转换的操作，将后面剩下的节点进行转换操作
        }

        //这个时候我们的prev就变成了我们反转后连标记的头结点了
        //3.接下来我们比较链表二档前半部分和反转后的后半部分
        ListNode *firstHalf=A;//前半部分从链表头开始
        ListNode* secondHalf = prev;//后半部分从反转链表的头结点开始
        while(secondHalf != NULL)//比较每个节点，直到我们的反转链表部分遇到了空
        {
            if(firstHalf->val!=secondHalf->val)
            {
                return false;//如果两个节点的值对应不上的话，那么我们就可以判断这个链表不是回文的
            }
            //比较完成之后指针就往后移动了
            firstHalf=firstHalf->next;
            secondHalf = secondHalf->next;
        }
        //运行到这里，就说明我们的链表是回文的了，那么我们直接返回结果就行了
        return true;
        
    }
};