[数据结构与算法]力扣 回文链表

题目链接：
https://leetcode-cn.com/leetbook/read/linked-list/fov6t/

时间复杂度：o(n)，空间复杂度o(1)
思想：
1、遍历链表，获取链表总长度
2、将链表前半段进行反转，这里记住一点：链表长度为偶数时，前半段和后半段长度相等；链表长度为奇数时，前半段要比后半段少一（这里选择了少一，其实前半段比后半段多一可以解答）
3、如果链表长度是奇数，那么将多一的那个链表取next，保持两个链表长度相等。因为如果是奇数，那么中间的数不影响奇偶性
代码：

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


bool isPalindrome(struct ListNode* head){
    if(!head || !head->next){
        return true;
    }
    struct ListNode*p = head;
    /*get the length of the LinkList*/
    int len = 0;
    while(p){
        len++;
        p = p->next;
    }

    /*reverse the pre-half LinkList*/
    
    p = head->next;
    struct ListNode* q = head->next;

    head->next = NULL;
    struct ListNode* r = head;
    int x = (len)/2-1;
    
    while(x){
        x--;
        p = p->next;
        q->next = r;
        r = q;
        q = p;
    }
    // printf("%d,%d\n",r->val,p->val);
    if(len%2){
        p = p->next;
    }
    while(p||r){
        if(p->val == r->val){
            p = p->next;
            r = r->next;
        }else{
            return false;
        }
    }

    // printf("%d,%d",r->val,p->val);

    return true;
}