# 0234. Palindrome Linked List
###### tags: `Leetcode` `Easy` `FaceBook` `Linked List` `Palindrome`
Link: https://leetcode.com/problems/palindrome-linked-list/
## 思路
### 思路一 O(N) O(N)
非常容易，遍历一遍，然后放在list里面，再用双指针判断
### 思路二
找到后一半的起始点，把后一半翻转，然后用双指针比较，再翻回来
找到后一半的起始点用了一个很巧妙的快慢指针的思想

## Code
### 思路二

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null) return true;
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);
        
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while(result && p2!=null){
            if(p1.val != p2.val) result = false;
            p1 = p1.next;
            p2 = p2.next;
        }
        
        reverseList(firstHalfEnd.next);
        return result;
    }
    public ListNode endOfFirstHalf(ListNode head){
        ListNode faster = head;
        ListNode slower = head;
        while(faster.next!=null && faster.next.next!=null){
            faster = faster.next.next;
            slower = slower.next;
        }
        return slower;
    }
    public ListNode reverseList(ListNode head){
        ListNode prev = null;
        ListNode curr = head;
        while(curr!=null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}