LeetCode234 回文链表

编写一个函数，检查输入的链表是否是回文的。

示例 1：

输入： 1->2
输出： false 

示例 2：

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

思路一：
利用递归，递归到链表的尾部，用 tail 值向尾部，然后回溯时，依次比较头结点 head 和 tail 的值，相等则 head 往下移动，不等则直接返回 false。

class Solution {
    // 标志位，如果为 true 时，则 head 向下移动
    boolean flag = false;
    // 全局变量 head，指向头结点
    ListNode head = null;
    public boolean isPalindrome(ListNode head) {
        if(head == null)
            return true;
        this.head = head;
        return recursion(head);
    }

    private boolean recursion( ListNode tail){
        if(tail == null){
            return true;
        }
        // 标志位，接收递归返回的值。
        flag = recursion(tail.next);
        // 如果 flag 为 true，则比较 head 和 tail的值
        if (flag){
            // head 和 tail 的值不相等 flag 则设为 false， 相等 head 向下移动
            if(head.val != tail.val)
                flag = false;
            else
                head = head.next;
        }
        return flag;
    }

}

思路二：
回文串的特点：前半部分反转等于后半部分
利用快慢指针，快指针移动的速度是慢指针的两倍，所以当快指针到达结尾时，慢指针刚好达到链表的后半部分的第一个元素（链表长度为偶数个时，当达链表的后半部分的下一个元素，奇数个到达链表的中间结点，需要再往下移动）。在慢指针移动的过程，将链表的前半部分反转。

class Solution {   
    public boolean isPalindrome(ListNode head) {
       ListNode fast = head;
       ListNode slow = head;
       ListNode pre = null;
       // 链表长度为奇数个的时候，最后 fast 指向链表最后一个的结点，偶数个指向 null
        while(fast != null && fast.next != null){
           fast = fast.next.next;

           // 链表前半部分反转
           ListNode next = slow.next;
           slow.next = pre;
           pre = slow;
           slow = next;

           
       }

        // 链表长度为奇数的情况
        if(fast != null)
            slow = slow.next;
        // 此时 pre 指向前半部分反转后开头的第一个元素    
        while(pre != null && slow != null){
            if(pre.val != slow.val)
                return false;
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }   
}