234. 回文链表(简单)

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

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list

思路：

用的是单链表，那么可以利用快慢指针实现，快指针走两步，慢指针走一步，当快指针走到末尾时，慢指针刚好会走到中间，用一个逆指针来逆置慢指针到达中间的每个位的next，便于后面进行判断前后是否一致。双链表的话这一步可以省略

代码：

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null || head.next==null)
            return true;
        //使用快慢指针法
        ListNode fast=head,slow=head;
        //还要定义一个逆向指针
        ListNode prev=null,temp = head;//temp要初始化为head
        //如果快指针没到头
        while(fast!=null &&fast.next!=null){
            //快指针走两步
            fast = fast.next.next;
            //慢指针走一步，这里是反转链表的写法
            temp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = temp;
        }
        //当fast不为null时，说明链表长度为奇数，slow正好在中心点，需要从中心点后一位开始判断
        if(fast!=null)
            slow = slow.next;
        //遍历两个指针，比较对应元素值是否相等
        while(prev!=null && slow!=null){
            if(prev.val!=slow.val){
                return false;
            }
            slow = slow.next;//慢指针往后走
            prev = prev.next;//逆向指针向前走
        }
        return true;
    }
}