力扣234.回文链表

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

示例 1：

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

示例 2：

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

 解题思路：快慢指针法

1.首先定义两个指针从头节点开始，一个快指针，一个慢指针（快指针一次走两步，慢指针一次走一步）。

2.当快指针走到NULL时，慢指针刚好走到链表中间。

3.反转中间链表后面的节点。

4.定义两个指针，一个从头结点开始，一个从反转后的链表头节点开始，向后遍历比较是否是回文链表。

 * struct ListNode {

 *     int val;

 *     struct ListNode *next;

 * };

 */

struct ListNode* reverse (struct ListNode*head)

{

    struct ListNode*pre=NULL;

    struct ListNode*cur=head;

    while (cur!=NULL)

    {

        struct ListNode*next=cur->next;

        cur->next=pre;

        pre=cur;

        cur=next;

    }

    return pre;

}

bool isPalindrome(struct ListNode* head){

    struct ListNode*p=head;

    struct ListNode*q=head;

    while (p->next!=NULL&&p->next->next!=NULL)

    {

        p=p->next->next;

        q=q->next;

    }

    struct ListNode*z=head;

    struct ListNode*s;

    s=reverse(q->next);

    while (s!=NULL)

    {

        if (z->val!=s->val)

        {

            return false;

        }

        z=z->next;

        s=s->next;

    }

    return true;

}