思路:
找中间结点
从中间结点开始对后半段进行逆置
比较前半段和后半段
相等是,不相等不是
只需将我们前面写过的链表中间结点,逆置链表的代码复用,并加上如下代码即可
最终代码:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
//返回中间结点
struct ListNode* middleNode(struct ListNode* head){
struct ListNode*slow,*fast;
slow = fast = head;
while(fast && fast->next)//考虑到结点个数的奇
{
slow = slow->next;
fast= fast->next->next;
}
return slow;
}
//链表逆置
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur,*newHead;
cur = head;
newHead = NULL;
while(cur)
{
struct ListNode* next = cur->next;
cur->next = newHead;
newHead = cur;
cur = next;
}
return newHead;
}
bool chkPalindrome(ListNode* head) {
struct ListNode* mid = middleNode(head);
struct ListNode* rhead = reverseList(mid);
while(head && rhead)
{
if(head->val != rhead->val)
return false;
head = head->next;
rhead = rhead->next;
}
return true;
}
};