链表-----5.如何判断回文链表？这里有你想要的结果！

题目链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnv1oc/

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

进阶：你能否用O(n)时间复杂度和 O(1)空间复杂度解决此题？

相关标签 栈、递归、链表、双指针

1. 借助数组

   大致思路：

   思路很简单，创建一个容量足够大的数组，然后遍历链表将值放进去。

   遍历完成后，设置一个数组的双指针（头和尾），头和尾所指的指相比较，遇到不同的返回false，直到完成。

   详细代码如下：

       public boolean isPalindrome(ListNode head) {
           int[] arr=new int[100000];
           int index=-1;
           while (head!=null){
               arr[++index]=head.val;
               head=head.next;
           }
           for (int i = 0,j=index; i 
    
   看得出来这个方法还是很费内存的。
    

2. 反转链表

   大致思路：

   找到链表的中间结点，然后将之后的链表反转，再一一比对。

   详细代码如下：

   	//判断是否是回文链表    
   	public boolean isPalindrome(ListNode head){
           ListNode mid=head;//定义要反转的链表中间指针
           ListNode rear=head;
           while (rear.next!=null&&rear.next.next!=null){
               mid=mid.next;
               rear=rear.next.next;
           }
           
           if (mid.next!=null){
               mid=mid.next;
               ListNode newHead= reverseList(mid);
               while (newHead!=null){
                   if (head.val!=newHead.val) return false;
                   head=head.next;
                   newHead=newHead.next;
               }
           }
           return true;
       }
       //反转链表
       public ListNode reverseList(ListNode head){
           ListNode p=null;
           ListNode c=null;
           ListNode next=head;
           while (next!=null){
               c=next;
               next=next.next;
               c.next=p;
               p=c;
           }
           return c;
       }
   

3. 使用递归

   大致思路：

   创建一个成员变量，调用方法时，将头结点赋值。

   创建一个方法递归到最后一个结点，然后从后往前和成员变量的值做比对。

   详细代码如下：

       ListNode myHead=null;
   
       public boolean isPalindrome(ListNode head){
           myHead=head;
           return isEq(head);
       }
       
   	public boolean isEq(ListNode node){
           if (node==null) return true;
           if (isEq(node.next)){
               if (myHead.val==node.val){
                   myHead=myHead.next;
                   return true;
               }else {
                   return false;
               }
           }else{
               return false;
           }
       }