提供一种不使用额外空间的纯递归的方式

思路很简单，先通过递归不断往后走，直到函数参数中的cur为空，开始返回。这样在递归栈回退的时候，其实将相当于，从末尾的节点不断一个一个往前走了。那判断回文链表就很好办了，我们用一个全局变量node，初始化为head，然后判断node.val是否等于cur.val和，如果相等，则令node=noe.next，继续回退。那现在的问题是如何判断到达终点了呢，其实也很简单，在递归函数中，我们放一个参数curPos，用来表示现在是哪个节点，然后再用一个全局变量nodePos表示node节点当前在链表中的哪个位置，当nodePos>curPos的时候，就说明已经判断结束了。但是，牛客对内存空间要求比较严格，纯递归会stack overflow，，LeetCode上原题限制较小，可以AC。这里只是提供一种参考思路吧。

public class Main {

    public static void main(String[] args) {
        ListNode head=ListNode.createList(new int[]{1,2,1,3});
        Main main=new Main();
        System.out.print(main.isPail(head));
    }

    public boolean isPail (ListNode head) {
        if(head==null||head.next==null){
            return true;
        }
        node =head;
        helper(head,0);
        return res;
    }
    private ListNode node;
    private int nodePos =0;
    private boolean res=false;
    private void helper(ListNode cur,int curPos){
        if(cur==null){
            return;
        }
        helper(cur.next,curPos+1);
        if(nodePos <0){//已经有节点不相同了，直接返回，不再判断
            return;
        }
        //开始判断
        if(nodePos >curPos){//判断结束
            res=true;
        }else{
            if(node.val==cur.val){
                node = node.next;//全局变量后移
                ++nodePos;//当前位置后移
            }else{
                nodePos =-1;//相当于做一个标记，说明有值不相同，不可能是回文链表
                return;
            }
        }
    }
}

其中，Main函数中用到的ListNode的定义如下：

public class ListNode {
    public int val;
    public ListNode next = null;
    public ListNode(int val) {
        this.val = val;
    }
    public static ListNode createList(int[] data){
        if (data==null||data.length==0){
            return null;
        }
        ListNode head=new ListNode(data[0]);
        ListNode cur=head;
        for (int i=1;i<data.length;++i){
            cur.next=new ListNode(data[i]);
            cur=cur.next;
        }
        return head;
    }

    @Override
    public String toString() {
        StringBuilder builder=new StringBuilder();
        ListNode cur=this;
        while(cur!=null){
            builder.append(cur.val);
            builder.append(",");
            cur=cur.next;
        }
        if(builder.length()>0){
            builder.deleteCharAt(builder.length()-1);
        }
        return builder.toString();
    }
}