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;
    
}

2021.07.11更新
更好理解的C++代码如下，这里其实修改了链表后半段的顺序，如果不修改链表后半段的顺序，可以新增一个flag，最后返回flag，在程序返回前再将后半段恢复回来。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* fast = head,*slow = head;
        
        while(fast && fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        slow->next = reverse(slow->next);
        ListNode* left = head,*right = slow->next;
        while(left && right)
        {
            if(left->val != right->val)
                return false;
            
            left = left->next;
            right = right->next;
        }

        return true;    
    }
private:
    ListNode* reverse(ListNode* head) {
        ListNode* prev = nullptr,*curr = head;
        while(curr)
        {
            ListNode* nxt = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nxt;
        }
        return prev;
    }
};

运行效率：

执行用时：200 ms, 在所有 C++ 提交中击败了95.26%的用户
内存消耗：115.3 MB, 在所有 C++ 提交中击败了48.11%的用户