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

解题分为三个步骤，①将链表分为两个部分；②将后一部分反转；③对比前后两个部分，判断是否为回文结构

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
//思路：
//①找到链表的中间结点（如果中间结点有两个则找到第二个中间结点）
//②通过中间结点将链表分为两部分，将前半部分的最后一个结点的next设为NULL，并将后半部分进行反转（包含中间结点）
//③将前半部分和反转后的后半部分按顺序对每一对结点进行比较，直到前半部分比较完（即，后半部分也没有结点或后半部分只有一个结点）
//  如果在步骤③中，直到比较结束也没有出现不同的结点，则返回true，否则返回false。
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        ListNode* front = A;
        ListNode* cur = A;
        ListNode* behind = NULL;
        ListNode* next = NULL;
        if(A)
        {
            //将链表从中间结点分为两部分
            ListNode* prev = A -> next;
            while( prev && prev -> next )
            {
                prev = prev -> next -> next;
                cur = cur -> next;
            }
            behind = cur -> next;
            cur -> next = NULL;
            //反转后半部分
            cur = behind;
            if(cur)
            {
                prev = cur -> next;
                while(prev)
                {
                    cur -> next = next;
                    next = cur;
                    cur = prev;
                    prev = prev -> next;
                }
                cur -> next = next;
                //比较前后两部分链表
                ListNode* Front = front;
                ListNode* Behind = cur;
                while(Front && Behind)
                {
                    if(Front -> val != Behind ->val)
                    {
                        return false;
                    }
                    Front = Front -> next;
                    Behind = Behind -> next;
                }
            }
        }
        return true;
    }
};