# LeetCode -  Palindrome Linked List
Date: 2019-04-27


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

**Example 1:**

```
Input: 1->2
Output: false
```

**Example 2:**

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

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

## 解题：

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

## 实现：

```
/**
 * 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;

}
```