234. Palindrome Linked List

question:

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

Follow up:
Could you do it in O(n) time and O(1) space?

answer:

思路：把前半部分的链表翻转，再分别用两个指针从中间往两边遍历比较。

 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     bool isPalindrome(ListNode* head) {
12         ListNode *p,*q,*r;
13         int i, l=0;
14         p=q=head;
15         r=NULL;
16         if(head==NULL||head->next==NULL){
17           return true;
18         }
19         while(p!=NULL){
20             l++;
21             p=p->next;
22         }
23         for(i=0;i<l/2;i++){
24             p=q->next;
25             q->next=r;
26             r=q;
27             q=p;
28         }
29         if(l%2==1){
30             p=p->next;
31         }
32         while(p!=NULL&&r!=NULL){
33             if(r->val!=p->val)
34             return false;
35             p=p->next;
36             r=r->next;
37         }
38         return true;
39     }
40 };