题解 | #链表的回文结构#
链表的回文结构
http://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa
/*
struct ListNode {
int val;
struct ListNode next;
ListNode(int x) : val(x), next(NULL) {}
};/
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
struct ListNodeslow=A,fast=A,pery;
while(fast&&fast->next)
{
pery=slow;
slow=slow->next;
fast=fast->next->next;
}
pery->next=NULL;
struct ListNoden1=NULL,n2=slow,n3;
while(n2)
{
n3=n2->next;
n2->next=n1;
n1=n2;
n2=n3;
}
slow=n1;
while(A)
{
if(A->val!=slow->val)
{
return false;
}
slow=slow->next;
A=A->next;
}
return true;
}
};
先用快慢指针法找到中点；再将中点之后的链表反转；原链表中点前一个成员指向空；原链表循环比较反转链表，若有不同则返回false，若成功执行到最后返回true
