leetcode234回文链表

递归思路

因为是单链表，没法往回找，可以用递归
递归在函数调用的时候会返回，走到最后一个我们让他和第一个比较。
往右走可以通过next,往左通过递归的特性

代码

代码一，我自己的

package leetcode;

import java.util.List;

public class Q234 {
    ListNode first = null;  //需要这个

    public boolean isPalindrome(ListNode head) {
        first = head;
        return recursion(head);
    }
    public boolean recursion(ListNode node){
        if (node == null){
            return true;
        }
        if (recursion(node.next)){
            if (node.val == first.val){
                first = first.next;
                return true;
            }else {
                return false;
            }
        }else { //其实只要一个比失败，就会一直返回这个
            return false;
        }
    }
}

题解的：

class Solution {
    private ListNode frontPointer;

    private boolean recursivelyCheck(ListNode currentNode) {
        if (currentNode != null) {
            if (!recursivelyCheck(currentNode.next)) {
                return false;
            }
            if (currentNode.val != frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }

    public boolean isPalindrome(ListNode head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/palindrome-linked-list/solutions/457059/hui-wen-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

但是递归需要走完序列

比如我们 1 2 3 2 1，只需要两边走到3就可以，但现在必须1 2 3 2 1都走完
因为递归必须一层一层调完

第二种思路

找到中点，然后就后半部分反转（头插法），再比较两个部分

怎么找链表的中点，快慢指针，快的一次走两步，是慢的二倍，所以快的到头以后慢的就到中点了，但是要区分
1 2 3 2 1 和 1 2 2 1两种情况的中点

快慢指针还可以判断环

package leetcode;

import java.util.List;

public class Q234 {
    public boolean isPalindrome(ListNode head) {
        if (head == null) { // 没有数
            return false;
        }
        if (head.next == null) { //只有一个数
            return true;
        }
        if (head.next.next == null) { //只有两个数
            if (head.val == head.next.val) {
                return true;
            } else {
                return false;
            }
        }
        ListNode mid = findMid(head);
        ListNode head2 = mid;
        ListNode p = mid.next;
        head2.next = null;
        while (p != null) {
            ListNode cnt = p;
            p = p.next;
            cnt.next = head2;
            head2 = cnt;
        }
        while (head != null && head2 != null) {
            if (head.val != head2.val) {
                return false;
            }
            head = head.next;
            head2 = head2.next;
        }
        return true;
    }

    public ListNode findMid(ListNode head) {
        ListNode fast = head;
        ListNode low = head;
        do {
            low = low.next;
            fast = fast.next;
            fast = fast.next;
            if (fast == null) {
                return low;
            }
            if (fast.next == null) {
                return low.next;
            }
        } while (fast != low);
        return null;
    }


}