题目描述：
给定一个链表，请判断该链表是否为回文结构。

例子： 123321 12321 1 11 此类的即为回文结构

方法一：线性表+双指针
这个方法其实很容易想到，把题目换了，如果不是一条链表判断是否是回文结构，换成是一个数组。
所以我们就可以先遍历一遍链表，然后将里面的值先存放进ArrayList中即可。
那么，我们就很容易想到利用双指针去判断是否是回文结构了！

图片说明
下面直接给出代码~

public boolean isPail (ListNode head) {
        if(head == null)
            return false;
        if(head.next == null)
            return true;
        // 创建一个ArrayList用来存储
        ArrayList<Integer> list = new ArrayList<>();
        // 将链表全部节点的值按顺序放进list
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        // 双指针，一个指向起点，一个指向终点！
        int left = 0, right = list.size()-1;
        while(left < right){
            // 如果不相等，那么则不是回文结构，直接返回false
            // 这里可能有个疑问，为什么是equals，不能直接！=
            // 下面顺便安利一个小知识点~
            if(!list.get(left).equals(list.get(right)))
                return false;
            left++;
            right--;
        }
        return true;
    }

复杂度分析：
时间复杂度：, 循环遍历次数取决于链表的长度。
空间复杂度：, 使用了线性表的空间，空间大小取决于链表的长度。

Tips:
这里来说一下为什么上面的比较是equals而不是用运算符。细心的人应该会发现，ArrayList中的类型是Integer，是包装类型，而不是基本类型。我们直到包装类型都是对象，所以直接使用运算符进行比较的时候，如果不是同一个对象，那么它会直接返回false。但是这也不是一定的，因为在 Java 8 中，Integer 缓存池的大小默认为 -128~ 127。也就是说，如果你的Integer类型的数字范围在-128~ 127中，那么直接使用运算符进行比较，则它都回去Integer缓存池中找，所以能够直接比较里面的值。超过这个范围则每一次就会new一个新的包装类型出来，直接使用运算符则肯定会返回false。

方法二：利用栈的特性
因为如果链表是回文的，那么将整个链表反转后肯定还是跟原链表是一样的。所以我们就利用栈的先进后出的特性，将整个链表的节点放进栈中，然后进行出栈操作相当于链表反转的作用，再进行依次遍历比较。
图片说明 

public boolean isPail (ListNode head) {

        if(head == null || head.next == null)
            return true;
        // 创建栈
        Stack<ListNode> stack = new Stack<>();
        ListNode node = head;
        // 将节点依次放进栈
        while(node != null){
            stack.push(node);
            node = node.next;
        }
        // 遍历然后依次比较
        while(head != null){
            // 如果中途发现不相等了，则直接返回false
            if(head.val != stack.pop().val)
                return false;
            head = head.next;
        }
        return true;
    }

复杂度分析：
时间复杂度：, 循环遍历次数取决于链表的长度。
空间复杂度：, 使用了栈，空间大小取决于链表的长度。

方法三：找中点+反转链表+遍历比较
看到方法的介绍其实就直到这个方法的步骤了，没错就是分为三个步骤！
1、快慢指针找中点

  • 先使用快慢指针找到链表的中点，然后根据中点找到表示后半段链表的头节点。

    可以利用 快慢指针，快指针一次走两步，慢指针依次走一步，当快指针走到终点的时候，此时如果链表的长度为偶数时，此时中间节点有两个，慢指针则走到了左端点。反之，慢指针则走到中间节点。（这两种情况在我们这道题目的总代吗，我们可以直接合并为一种，则第二个链表的长度比第一个链表的长度小1）

    class Solution {
public ListNode middleNode(ListNode head) {
   if(head == null)
       return head;
   ListNode slow = head;
   ListNode fast = head;
   while(fast.next != null && fast.next.next != null){
       slow = slow.next;
       fast = fast.next.next;
   }
   if(fast.next == null)  // 长度为奇数
       return slow; // slow为中点
   else
       return slow.next;  // 长度为偶数  slow slow.next为中点
}
}

    2、反转链表 NC78 反转链表
    3、遍历比较

    public boolean isPail (ListNode head) {

   if(head == null || head.next == null)
       return true;
   // 慢指针
   ListNode slow = head; 
   // 快指针
   ListNode fast = head;
   while(fast != null && fast.next != null){
       fast = fast.next.next;
       slow = slow.next;
   }
   fast = slow.next; // 此时fast则会后半段链表的头结点
   slow.next = null; // 置为null
   ListNode nHead = null;
   while(fast != null){
       nHead = fast.next;
       fast.next = slow;
       slow = fast;
       fast = nHead;
   }
   nHead = slow; // 后半段链表反转后的链表
   fast = head;  // 原来的链表
   // 遍历判断是否是回文
   while (fast != null && nHead != null) {
       if (fast.val != nHead.val) {
           return false;
       }
       fast = fast.next;
       nHead = nHead.next;
   }
   return true;
}

```
复杂度分析：
时间复杂度：, 循环遍历次数。
空间复杂度：, 没有使用额外的空间。