快慢指针、反转链表

单链表中快慢指针可用于找链表中点，模板如下：

	ListNode*slow=head,*fast=head;
    while(fast&&fast->next){
        slow=slow->next;
        fast=fast->next->next;
    }

反转链表，模板如下：

	ListNode* cur = head, * pre = NULL; //反转链表的模板
    while(cur) { 
        ListNode* temp = cur->next; //反转链表的模板
        cur->next = pre;
        pre = cur;
        cur = temp;
    }

实际上，反转链表就是，头节点删除，然后再将cur->next->val,进行头插法，从而达到反转链表的目的。

上面两种指针模板组合可用于链表回文的判定：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* q = head; //快指针
        ListNode* cur = head, * pre = NULL; //反转链表的模板
        while(q && q->next) { 
            q = q->next->next; //2倍慢指针的速度
            ListNode* temp = cur->next; //反转链表的模板
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        if(q) cur = cur->next; //奇数链表处理
        while(pre) { //开始对比
            if(pre->val != cur->val) return false;
            pre = pre->next;
            cur = cur->next;
        }
        return true;
    }
};