一.题目
二.分析
回文可以理解为数学上的对称。
我们初步分析思路:
(1)找到链表的中间节点http://t.csdnimg.cn/iOcxq
(2)将后半段链表逆置http://t.csdnimg.cn/HLxWX
(3)链表前半段的头节点(A)和后半段的头结点(rmid)同时向后遍历,判断节点位置的val值是否相等。
我们来判断一下(3)向后遍历的停止条件:
在(1)(2)的前提下:
<1>奇数个节点
<2>偶数个节点
由图可知:无论是奇数还是偶数个节点,遍历的结束条件都是两个指针的next指针指向NULL!
三.参考代码
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
typedef struct ListNode ListNode;
class PalindromeList {
public:
//找到链表的中间节点(快慢指针)
ListNode* MiddleNode(ListNode* head) {
ListNode* slow, *fast;
slow = fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
//反转链表(三个指针)
ListNode* reverseList(ListNode* head) {
ListNode* n1, *n2, *n3;
n1 = NULL;
n2 = head;
n3 = head->next;
while (n2) {
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3 != NULL) {
n3 = n3->next;
}
}
return n1;
}
bool chkPalindrome(ListNode* A) {
ListNode* mid = MiddleNode(A);
ListNode* rmid = reverseList(mid);
while (rmid && A) {
if (rmid->val != A->val) {
return false;
}
rmid = rmid->next;
A = A->next;
}
return true;
}
};