这题感觉细节比较多

比如链表要从中间节点那里开始反转 找到的中间节点是 n/2+1个节点

最终对比头尾指针时，偶数情况下只需要比较左边指针等于右边指针即可，奇数情况下相当于左边指针多走一步，需要判断右边指针不能等于空

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
         if (head == null || head.next == null) {
            return true;
        }
        ListNode mid=findMid(head);
        System.out.println(mid.val);
        ListNode newhead=reverse(mid);
        while(head!=newhead && newhead!=null){  
            // 这一步不可以写(head.next！=newhead)
            // 否则head为null报错
            System.out.println(head.val+" "+newhead.val);
            if(head.val!=newhead.val){
                return false;
            }
            // if(head.next==newhead){
            //     break;
            // }
            head=head.next;
            newhead=newhead.next;
        }
        return true;
    }
    public ListNode findMid(ListNode head){
        ListNode low=head;
        ListNode fast=head;
        while(fast!=null && fast.next!=null){
            low=low.next;
            fast=fast.next.next;
        }
        return low;
    }

    public ListNode reverse(ListNode head){
        ListNode newhead=null;
        ListNode next=null;
        ListNode cur=head;
        while(cur!=null){
            next=cur.next;
            cur.next=newhead;
            newhead=cur;
            cur=next;
        }
        return newhead;
    }
}

另一种前后回文判断的方式是判断左指针不等于右指针，：

判断是否为回文链表

之前做过判断是否为回文字符串的题目，用到的方法有，双指针，即一个从开始走，一个从末尾走，判断两者是否相等即可，当然其中需要注意的一个问题便是，要将大写字母都转化为小写字母

而单向链表不同于数组结构，无法直接从后向前，于是本人进行了如下尝试：

1、将链表中的val值全部存入LinkList中，再通过判断回文字符串的类似方法判断，LinkList是否为回文，代码如下：

public static boolean solution01(ListNode head){

        LinkedList<Integer> list = new LinkedList<>();
        while (head != null){
            list.add(head.val);
            head = head.next;
        }

        for (int i = 0; i < list.size()/2; i++) {
            if (list.get(i) != list.get(list.size() - i - 1))
                return false;
        }
        return true;
    }

通过运行发现，正常的链表都可以判断，但是在提交的时候发现，有一个链表运行超时，点击查看，是由于leetcode提供了一个几百个结点的链表，what the fuck！这条路堵死了。

2.直接将链表全部翻转，然后判断对应的val值是否相等

理论上这种方式是可行的，但是，我在编写的过程中发现一个问题，在将原链表翻转后，链表自己就只剩头节点了，或者为null。因为之前实现的翻转都是返回的一个新的链表，这导致无法进行翻转后的链表与原链表进行比较了。（寄！）

3.翻转后一半链表，与前一半链表进行比较

由于上述方法的失败，不得不考虑新的方法，其实我们不需要翻转整个链表，我们只需要翻转后一半链表，然后与前半部分链表进行比较即可。
问题转化如下：

1. 获得后半部分链表
   可以使用快慢指针，快指针走两格，慢指针走一格，那么当快指针为空，或者快指针下一个为空时，慢指针就走到一半了，当然还涉及一个奇数偶数个结点的问题，如果是奇数个结点，那么慢指针应该继续向后走一格。代码如下：

		ListNode slow = head;
        ListNode fast = head;

        //快指针走到头，则慢指针走到一半，获得后半部分的链表
        if (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        
        //如果fast不为空，说明链表的长度是奇数个，则慢指针继续往后走一个
        if (fast != null){
            slow = slow.next;
        }

这样就获得了后半部分的链表——slow。
2. 翻转后半部分链表
在或者后半部分链表后，对其进行翻转，即使其原链表发生改变也没什么影响

slow = reverse(slow);

//翻转函数如下
   public static ListNode reverse(ListNode head){
       ListNode prev = null;
       while (head != null){
           ListNode next = head.next;
           head.next = prev;
           prev = head;
           head = next;
       }
       return prev;
   }

3.判断是否相等
这段代码较为简单，以慢指针为目标进行迭代就行，如下：

fast = head;
while (slow != null){
    if (fast.val != slow.val)
        return false;
    fast = fast.next;
    slow = slow.next;
}
return true;

4.总结

针对链表的回文判断，我觉很需要掌握快慢指针的运用，同时如何获得后一半的链表的思想，也是我们应该掌握的，此类方法在后续的学习中应当常用。全文手码，如有写的不好的，不对的地方希望大家批评指正，共同进步。

方法一：
_{最简单也最容易想到的方法，采用栈的数据结构，将链表节点依次入栈，因为栈先进后出的特性，当链表节点全部入栈后，栈中就保存了原链表节点的逆序排列，然后将栈顶节点依次出栈并顺序与链表节点进行比较，如果在比较过程中发现节点的值不同，说明不是回文链表}

【代码实现】

//首先给出节点类的定义
public class Node {
    public int val;
    public Node next;

    public Node(int data) {
        this.val = data;
        this.next = null;
    }
    public Node() {
    }
}

_{以下所有方法均假设链表}没有_头结点！

    public static boolean isHuiwen1(Node list) {
        Node p = list;
        Stack<Node> st = new Stack<Node>();
        while (p != null) {
            st.push(p);
            p = p.next;
        }
        p = list;
        while (!st.isEmpty()) {
            if (p.val != st.pop().val)
                return false;
            p = p.next;
        }
        return true;
    }

方法二：
_{方法一是将链表节点全部入栈，但判断一个链表是不是回文链表，我们只需要顺序比较表头跟表尾节点值即可，比如说list1=1->2->3->2->1，我们只需要比较1跟1，2跟2，3跟3。所以方法二就采用了这一思想，跟方法一差不多，也用到了栈的数据结构，只不过首先要进行链表的遍历，找到链表的中间节点p，p将整个链表分成左右两部分，我们只需要将右半部分链表入栈即可}

_{先介绍求链表中间节点的方法
定义两个节点p，q，分别指向头结点head和head.next，然后在p.next不为空且q.next.next不为空的条件下，循环执行——“q后移一步，p后移两步”的操作，那当p走到链表最后一个节点或者倒数第二个节点时，q刚好指向链表的中间节点，这与“求链表的倒数第K个节点的方法有异曲同工之妙”}

    Node p = head, q = head.next;//q point to the middle Node
    while (p.next != null && p.next.next != null) {
        q = q.next;
        p = p.next.next;
    }

_{此方法的代码描述}

    public static boolean isHuiwen2(Node list) {
        Node head = new Node();
        head.next = list;//create a head Node
        Stack<Node> st = new Stack<Node>();
        Node p = head, q = head.next;//q finally point to the middle Node
        while (p.next != null && p.next.next != null) {
            q = q.next;
            p = p.next.next;
        }
        while (q != null) {
            st.push(q);
            q = q.next;
        }
        p = head.next;
        while (!st.isEmpty()) {
            if (p.val != st.pop().val)
                return false;
            p = p.next;
        }
        return true;
    }

方法三：

<sub>方法三用到了链表的逆序，实际上是链表部分逆序。这一方法的思想是：首先通过链表遍历找到链表的中间节点，然后将右半部分链表进行逆序，如下图所示

然后，我们就可以通过定义两个分别指向表头跟表尾的节点，依次对链表首尾节点进行比较了呀！</sub>

    public static boolean isHuiwen3(Node list) {
        Node head1 = new Node();
        Node head2 = new Node();
        head1.next = list;
        Node p = head1, q = head1.next, r;//q point to the middle Node

        while (p.next != null && p.next.next != null) {
            q = q.next;
            p = p.next.next;
        }

        p = q.next;
        while (p != null) {
            q.next = null;
            r = p.next;
            p.next = q;
            if (r == null) {//note that p point to the last Node
                q = p;
                break;
            }
            q = r;
            p = q.next;
        }

        p = head1;
        head2.next = q;
        q = head2;
        while (p.next != null && q.next != null) {
            if (q.next.val != p.next.val) {
                return false;
            }
            q = q.next;
            p = p.next;
        }
        return true;
    }

可以看出在时间复杂度相同，都为O(N)的情况下，方法三的空间复杂度为O(1)，其他两种方法都采用了栈的数据结构，时间复杂度都为O(N)

还有要注意的一点是，不管链表是不是回文链表，方法三在结果返回前都需要将链表还原为初始结构，不能给人家把结构改了又不改回去，可以自己尝试写一下