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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
#include<iostream>
using namespace std;
struct ListNode* MidNode(struct ListNode* phead)
{
	struct ListNode* fast, * slow;
	slow=fast =phead; 
	while (fast && fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	return slow;
}
struct ListNode* reverseList(struct ListNode* phead)
{
	struct ListNode* newhead = NULL;
	struct ListNode* cur = phead;
	struct ListNode* next = cur->next;

	while (cur)
	{
		next = cur->next;
		cur->next = newhead;
		newhead = cur;
		cur = next;
	}
	return newhead;
}

class PalindromeList {
public:
	bool chkPalindrome(struct ListNode* A) {

		ListNode* phead = A;
            ListNode* mid = MidNode(phead);
            ListNode* newphead = reverseList(mid);
            ListNode* p1 = phead;
            ListNode* p2 = newphead;
            while (p2 && p1) 
            {
                if (p1->val != p2->val) 
                {
                    return false;
                }
                p1 = p1->next;
                p2 = p2->next;
            }
            return true;
	}
};