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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
         ListNode* first = A, * second = A;
	     ListNode* pos = NULL;
	while (first->next != NULL)
	{
		first = first->next;
	}
	first->next = A;
	//根据回文函数的对称性解题
	while (second != first)
	{  //直到双指针相遇
		if (second->val != first->val)
		{//对称性比较
			return false;
	    }
		pos = first;         //固定检查过节点
		first = first->next;  
		while (first->next != pos) //寻找下一个节点
		{
			first = first->next;
		}
		if (first != second)
		{
			second = second->next;
		}
	}
	return true;
    }
};