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

Follow up:
Could you do it in O(n) time and O(1) space?
题目描述比较简单:判断链表中的val组成的数字是否是回文数即形如12321 123321即是回文数。
如果题目中没有O(1) space的要求的话,那么可以把链表的值顺序读出放在数组中,然后进行判断。
一种比较巧妙的思路是:逆序(reverse)后半段,然后比较前后两段的值是否相同。
实现代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverseList(struct ListNode* head) 
{
    if(NULL==head) 
        return head;

    struct ListNode *p=head;
    p=head->next;
    head->next=NULL;
    while(NULL!=p)
    {
        struct ListNode *tmp=p->next;
        p->next=head;
        head=p;
        p=tmp;
    }
    return head;
}

bool isPalindrome(struct ListNode* head) 
{
    if(NULL == head || NULL == head->next)
        return true;
    
    struct ListNode * slow = head;
    struct ListNode * fast = head;
    
    while(fast->next &&fast->next->next)
    {
        fast = fast->next->next;
        slow = slow->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;
    
}