234. 回文链表

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

题解思路：

方法一：暴力法

遍历链表，将链表里元素的值放入数组里面，然后再判断数组里面的数字是不是回文数字。

函数代码一：

class Solution { public: bool isPalindrome(ListNode* head) { //当链表长度为0正确 if(!head) { return true;; } ListNode *p=head; int len=0; vector<int>res; while(p) { res.push_back(p->val); p=p->next; len++; } //当链表长度为1时正确 if(len==1) { return true; } for(int i=0;i<len/2;i++) { if(res[i]!=res[len-i-1]) { return false; } } return true; } };

推荐方法二：双指针+链表翻转 举例：[1->2->3->2->1] 当链表长度为奇数时，fast最后指向1，slow指向3;这时判断fast是否为空，不为空，slow走下一个结点就变为2。slow方向的就是2->1,p方向是2->1(前半部分翻转)

举例：[1->2->2->1] 当链表长度为偶数时，fast最后指向空，slow指向后半部分的2, ;这时判断fast是否为空，为空，slow不走。slow方向的就是2->1,p方向是2->1(前半部分翻转)

函数代码二：

class Solution { public: bool isPalindrome(ListNode* head) { //当链表长度为0和1时都正确 if(!head||!head->next) { return true; } ListNode *pre=NULL; ListNode *slow=head; ListNode *fast=head; ListNode *p=NULL; while(fast&&fast->next) { p=slow; slow=slow->next; fast=fast->next->next; p->next=pre; pre=p; } if(fast) { slow=slow->next; } while(p) { if(p->val!=slow->val) { return false; } p=p->next; slow=slow->next; } return true; } };