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

Example 1:

1
2

Input: 1->2
Output: false

Example 2:

1
2

Input: 1->2->2->1
Output: true

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

解题：

找到中间节点后反转判断节点回文

实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

bool isPalindrome(struct ListNode* head){

        if (head == NULL || head->next == NULL) {
            return true;
        }
        struct ListNode* slow=head;
        struct ListNode* fast=head;
        struct ListNode* pre=NULL;
        struct ListNode* next=NULL;
  
    
        //get middle
        while(  fast!=NULL && fast->next!=NULL){
             slow = slow->next;
             fast = fast->next->next;               
        }
        if(fast) {
                 slow=slow->next;
        }
    
        struct ListNode* cur=slow;
        //and reverse 
        while(cur!=NULL){
            pre = cur;
            cur = cur->next;
            pre->next = next;
            next = pre;
        }
        //compare 
        cur = head;
        while(pre!=NULL){
               //printf("%d %d\n", head->val, pre->val);
               if (cur->val != pre->val){
                     return false;
               }
               cur=cur->next;
               pre= pre->next;
        }

        return true;

}