[链表]-234. 回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

---

解析：

方法一：

因为链表的特殊性，只能从头节点开始遍历。类似于 删除链表倒数第n个节点 那样利用两个快慢指针，找到中间节点。这里需要用到栈，每次慢的指针走一步，就把它的值存到栈里，到达中点后，链表的前半段都存入栈中，利用栈的先进后出的性质，就可以和后半段链表进行对比。

方法二：

利用两个快慢指针，找到中间节点。p1每次走一步，p2每次走两步。这里节点个数的奇偶性不会影响(奇数时，中间节点公用可以不用管)。p的下一个节点为后半段的头节点，把后半段链表反转一下再和前半段进行比较。

C代码

bool isPalindrome(struct ListNode* head) {
    if( head == NULL || head->next == NULL ) return true;
    struct ListNode* t =head;
    struct ListNode* p1=head;
    struct ListNode* p2=head;
    //利用快慢指针找到链表的中间节点；
    while(p2->next&&p2->next->next){
        p1=p1->next;
        p2=p2->next->next;
    }
    //此时中间节点p1，从p1下一个节点开始为后半段，反转后半段节点和前半段进行比较
    struct ListNode* h=p1->next;
    struct ListNode* p=h->next;
    struct ListNode* q=h;
    while(p){
        q->next=p->next;
        p->next=h;//向前挂链
        h=p;
        p=q->next;
    }
    while(h){
        if(h->val != t->val) return false;
        h=h->next;
        t=t->next;
    }
    return true;
}