[LeetCode234]Palindrome Linked List

 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 class Solution {
10 public:
11 
12     ListNode* reverseList(ListNode* head) {
13          ListNode *cur = head;
14          ListNode *tmp, *prev = NULL;
15          while(cur)
16          {
17              tmp = cur->next;
18              cur->next = prev;
19              prev = cur;
20              cur = tmp;
21          }
22          return prev;
23     }
24     
25     bool isPalindrome(ListNode* head) {
26         if(!head || !head->next)
27             return true;
28         //快慢指针法 寻找中点
29         ListNode *slow, *fast;
30         slow = fast = head;
31         while(fast && fast->next)
32         {
33             slow = slow->next;
34             fast = fast->next->next;
35         }
36         if(fast)//链表元素奇数个
37         {
38             slow->next = reverseList(slow->next);
39             slow = slow->next;
40         }
41         else//链表偶数个
42         {
43             slow = reverseList(slow);
44         }
45         while(slow)
46         {
47             if(head->val != slow->val)
48             {
49                 return false;
50             }
51             slow = slow->next;
52             head = head->next;
53         }
54         return true;
55     }
56 };