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

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

例子： 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;
  }
  
  

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