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

Example 1:

Example 2:

Follow up:
Could you do it in O(n) time and O(1) space?

 

参考这里

用快慢指针找到中间结点。然后反转后半段链表。与前半段链表逐一比较即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head||!head->next){
            return 1;
        }
        ListNode *slow=head,*fast=head;
        while(fast->next&&fast->next->next){
            slow=slow->next;
            fast=fast->next->next;           
        }
        ListNode *tail=reverseList(slow);
        while(head){
            if(head->val!=tail->val){
                return 0;
            }
            head=head->next;
            tail=tail->next;
        }
        return 1;
    }
    
    ListNode *reverseList(ListNode *head){
        if(!head||!head->next){
            return head;
        }
        ListNode *p1=head,*p2=head->next,*p3=head->next->next;
        p2->next=p1;
        while(p3){
            p1=p2;
            p2=p3;
            p3=p3->next;
            p2->next=p1;
        }
        head->next=0;
        return p2;    
    }
};