Leetcode：234 回文链表

leetcode:234 回文链表

 1/**
 2 * Definition for singly-linked list.
 3 * struct ListNode {
 4 *     int val;
 5 *     ListNode *next;
 6 *     ListNode(int x) : val(x), next(NULL) {}
 7 * };
 8 */
 9/**
10*解题思路：1->2->2->1
11*       1.遍历中间节点,区分左右链表
12*       2.反转链表
13*/
14class Solution {
15public:
16    bool isPalindrome(ListNode* head) {
17
18        ListNode *pslow = head, *pfast = head;
19        if(!head)
20            return true;
21        //1.slow移动到中间节点
22        while (pfast&&pfast->next&&pfast->next->next) {
23            pslow = pslow->next;
24            pfast = pfast->next->next;
25        }
26        //2.反转链表
27        pslow->next = reverse(pslow->next);
28        ListNode *pre = head;
29        while (pslow->next) {
30            pslow = pslow->next;
31            if (pre->val != pslow->val) return false;
32            pre = pre->next;
33        } 
34        return true;
35
36    }
37    ListNode* reverse(ListNode* head){
38        if(!head)
39            return NULL;
40        ListNode* q = head->next;   //下一节点
41        ListNode* p = head;         //前一节点
42        ListNode* pr;
43        head->next = NULL;  //头节点指向空
44        while(q){
45            pr = q->next;   //先保存节点值
46            q->next = p;    //指向q
47            p = q;          //指向反转节点     
48            q = pr;         //指向下一节点
49        }
50        head = p;           //最后q必然指向NULL，所以返回了p作为新的头指针 
51        return head;
52   }
53
54};