回文链表单链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例一：

输入：head = [1,2,2,1]
输出：true

示例二：

输入：head = [1,2]
输出：false

思路：

1求出链表的中间结点 ，
2反转后半段结点
3判断是否回文
4 反转后半段结点

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr != NULL) {
        struct ListNode* nex = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nex;
    }
    return prev;
}
//函数求的是后半段结点的前一个结点，以便后面再次反转后半段链表
struct ListNode* half(struct ListNode* head) {
    struct ListNode *fast = head, *slow = head;
    struct ListNode *tem;
    while(fast->next && fast->next->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;  
}

bool isPalindrome(struct ListNode* head){
    if (head == NULL)
        return true;
    struct ListNode * halfhead =  half(head);
    struct ListNode * endhead = reverseList(halfhead->next);
    struct ListNode * p = head ,*q = endhead;  
    while(q) //判断回文
    {
        if(q->val != p->val)
            break;
        q = q->next;
        p = p->next;
    }
    //链表回正
    halfhead->next = reverseList(endhead);
    if(q)
        return false;
    else
        return true;
}