[LeetCode234]Palindrome Linked List

题目：

Given a singly linked list, determine if it is a palindrome.

判断一个单链表是不是回文

思路：

1、遍历整个链表，将链表每个节点的值记录在数组中，再判断数组是不是一个回文数组，时间复杂度为O（n），但空间复杂度也为O（n），不满足空间复杂度要求。

2、利用栈先进后出的性质，将链表前半段压入栈中，再逐个弹出与链表后半段比较。时间复杂度O（n），但仍然需要n/2的栈空间，空间复杂度为O（n）。

3、反转链表法，将链表后半段原地翻转，再将前半段、后半段依次比较，判断是否相等，时间复杂度O（n），空间复杂度为O（1）满足题目要求。

代码：这里采用第三种

 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 };