问题描述

Given a singly linked list, determine if it is a palindrome.

【解题思路】

1. 遍历链表，快慢指针，找到链表后半部分。

2. 反转链表，可以参考。

3. 然后比较前半部分和后半部分的val值。

快慢指针是链表中常用的技巧，也是常用算法之一。

class Solution {public:    bool isPalindrome(ListNode* head) {        if(head==NULL||head->next==NULL)            return true;        ListNode* slow=head;        ListNode* fast=head;        while(fast->next!=NULL&&fast->next->next!=NULL){            slow=slow->next;            fast=fast->next->next;        }        slow->next=reverseList(slow->next);        slow=slow->next;        while(slow!=NULL){            if(head->val!=slow->val)                return false;            head=head->next;            slow=slow->next;        }        return true;    }    ListNode* reverseList(ListNode* head) {        ListNode* pre=NULL;        ListNode* next=NULL;        while(head!=NULL){            next=head->next;            head->next=pre;            pre=head;            head=next;        }        return pre;    }};