题解 | #判断一个链表是否为回文结构#

两个思路：

1，利用一个公共变量然后递归回溯实现，公共变量pre从前向后遍历链表，递归到列表尾部后开始回溯，从后往前遍历链表，将pre和回溯到的节点比较。

注意的点：

1. 返回boolean的值
2. 输入参数，当前节点head
3. 递归终止条件：head==null，此时返回true，因为递归中若前一个比较不相等，后面没有比较的必要，所以比较放在if语句中

2，反转后半部分链表，比较，反转利用快慢指针法找到中间节点，这一部分建议自己画个链表试一下，分为单数和双数的情况，你就能明白我的slow和fast的初始化了。

代码：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    ListNode pre;
    public boolean isPail (ListNode head) {
//         //方法一：递归实现，利用一个公共变量从前往后遍历，递归法到链表最后开始回溯，和公共变量进
//         //行比较
//         pre=head;
//         return dfs(head);
        
        //方法二，反转一半链表，比较
        if(head==null){
            return true;
        }
        //快慢指针初始化
        ListNode fast=head.next;
        ListNode slow=head;//记得将反转的后一半从原始链表中移去
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode head1=recur(slow,null);
        slow.next=null;
        while(head!=null){
            if(head.val!=head1.val){
                return false;
            }
            head=head.next;
            head1=head1.next;
        }
        return true;
    }
    private ListNode recur(ListNode cur,ListNode pre){
        if(cur==null){
            return pre;
        }
        ListNode res=recur(cur.next,cur);
        cur.next=pre;
        return res;
    }
    
    private boolean dfs(ListNode head){
        if(head==null){
            return true;
        }
        if(dfs(head.next)){
            boolean flag=head.val==pre.val;
            pre=pre.next;
            return flag;
        }
        return false;
    }
}