234.回文链表

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

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

1.使用Arraylist将链表中的数据保存在数组中，再用快慢指针判断是否回文。

这种解法时间复杂度和空间复杂度都是 O(n)。

2.用快慢指针遍历链表，快指针走到链表结尾时，慢指针走到一半，把满指针之后的链表反转。再把两半链表进行比较。

class Solution {
    public boolean isPalindrome(ListNode head) {
        //判断链表是否为空或只存在一个元素
        if(head == null || head.next == null){
            return true;
        }
        ListNode slow = head;
        ListNode quick = head;
        //快慢指针遍历
        while(quick.next != null && quick.next.next != null) {
            slow = slow.next;
            quick = quick.next.next;
        }
        //链表反转
        ListNode p1 = slow.next;
        ListNode temp = p1.next;
        p1.next = null;
        while(temp != null) {
            ListNode temp2 = temp.next;
            temp.next = p1;
            p1 = temp;
            temp = temp2;
        }
        //此时p1为后半段开头，遍历两个链表并比较
        while(p1 != null) {
            if(p1.val != head.val) {
                return false;
            }
            p1 = p1.next;
            head = head.next;
        }
        return true;
    }
}

重点，当链表个数为单数时在快慢指针遍历的时候会出现NullPointerException错误，原因是只判断了quick.next.next是否为空，但当链表个数为单数时，走到最后一个节点，会报错。

所以但快指针走到最后一个节点时，判断下一个是否为空，并用短路或结束判断避免访问到quick.next.next报错。