判断链表是否是回文链表？回文结构，回文串
判断链表是否是回文链表？回文结构，回文串
提示：关于回文结构：是有非常多的互联网大厂的题，也涉及到很重要的算法基础原型，所以要透彻理解！
本文的基础知识点：
找到链表的中点，上中点，或者下中点的知识点：
（1）求链表中的中点、上中点、下中点
文章目录 题目一、审题二、解题 总结
题目
给你一个链表，头结点为head，请你判断该链表是否为回文结构？
一、审题
示例：1-2-3-3-2-1
是回文结构
1-2-3
不是回文结构
二、解题 什么是回文结构？回文啥意思？
所谓回文，就是正着念，回着念，都一样
12321，正序念：12321
逆序念12321,
左右都是对称的
正序=逆序
就是回文！
本题要用的链表的节点数据结构：常规的节点
public static class Node{//单链表，一个next指针public int value;public Node next;public Node(int v){value = v;}}
本题全程需要用来验证的链表：
public static Node createLinkNode(){Node head = new Node(1);Node n2 = new Node(2);Node n3 = new Node(3);Node n4 = new Node(2);Node n5 = new Node(1);head.next = n2;n2.next = n3;n3.next = n4;n4.next = n5;return head;//1-2-3-2-1}
谈到逆序，咱们之前学过一个数据结构，栈：它可以先进后出完成逆序操作！
所以呢，完全可以，用o(n)的外部空间结构来存储这个额外的逆序操作，耗费o(n)的空间复杂度
当然，判断链表从头到尾，怎么着也要o(n)的时间复杂度，来遍历确认两两是否相等。故o(N)时间复杂度是绕不过去的
只能在空间上做一些优化，赢得面试官的青睐！！！
笔试求AC,咱可以不考虑空间复杂度，随意做，代码简单就能通过
但是面试，是要最优解，既要考虑时间复杂度，又要考虑空间复杂度。
一点空间都不节约的暴力逆序对比
这很容易，笔试AC可以写的简单代码
将整个链表全部放入栈，然后不断弹出逆序，与原链表对比即可
手撕代码：
//复习回文结构//（1）一点空间都不节约的暴力逆序对比//这很容易，笔试AC可以写的简单代码//将整个链表全部放入栈，然后不断弹出逆序，与原链表对比即可public static boolean isPalidrome(Node head){if (head == null || head.next == null) return true;Stack<Node> stack = new Stack<>();Node cur = head;while (cur != null){stack.push(cur);cur = cur.next;}//对比while (!stack.isEmpty()){if (head.value != stack.pop().value) return false;head = head.next;}//全部对比完成，没问题就OKreturn true;}
节约一半空间，使用快慢指针暴力逆序对比
你发现了问题，
既然回文的结构是前半段=后半段
那干嘛要讲整个链表都放入栈呢？？？
只需要放一半，你怎么找到中点，或者上中点呢？？？
之前咱就说过，找到链表的中点，上中点，或者下中点的知识点：
（1）求链表中的中点、上中点、下中点
因此，完全可以利用快慢指针，确定一个链表的中点，上中点，然后，咱们只需要将后半部分放入栈即可！！！然后逆序弹出对比
链表长度是奇数N则就是中点：下图左边例子
链表长度是偶数N则就是上中点：下图右边的eg1,eg2
eg1中，显然不是回文结构，咱只需要对比一半
eg2中，是回文结构，也只需要对比一半
手撕代码：
//(2)完全可以利用快慢指针，确定一个链表的中点，上中点，// 然后，咱们只需要将后半部分放入栈即可！！！然后逆序弹出对比public static boolean isPalidromePen2(Node head){if (head == null || head.next == null) return true;//找中点slowNode fast = head;Node slow = head;while (fast.next != null && fast.next.next != null){fast = fast.next.next;slow = slow.next;}//fast走不动了，slow就是中点或者上中点//然后，加入一半入栈Node cur = slow.next;Stack<Node> stack = new Stack<>();while (cur != null){stack.push(cur);cur = cur.next;}//然后对比head和stack的逆序while (!stack.isEmpty()){if (head.value != stack.pop().value) return false;head = head.next;}//全部通过，则OKreturn true;}
本题面试最优解！o(1)空间复杂度，快慢指针逆序对比，再恢复原链表
好，这才是本题的重点！！
你必须在面试时尽可能地拿出最优解，优化时间复杂度，空间复杂度
我们不用栈
（1）既然快慢指针可以用来锁定中点，则我们就有办法找到前后各自一半
（2）让slow指针指向null，断开前后半段，然后让后面半段，逆序链表，逆序后的后半段头节点为cur
（3）然后让head后cur对比，相等就没事，一旦不相等，非回文！
（4）对比完成，拿到结果，然后需要将后半段逆序恢复，然后接上前半段，返回结果后，咱不可以破坏链表的原始结构。
偶数长度呢？
比如12321判断完之后，你返回结果前要恢复链表哦
这样的话，咱完全没有耗费任何的额外空间
只不过就是手撕代码烦了点，你要搞清楚这个代码的核心思想，然后写清楚每一个步骤，保证不出错
错了也没事啊，调试找错，训练自己的能力。
手撕哦！！必须手撕，自己想清楚核心思想，一气呵成，调试出来，别抄别人的东西，你就得自己闭眼也能写出来。
//我们不用栈//（1）既然快慢指针可以用来锁定中点，则我们就有办法找到前后各自一半//（2）让slow指针指向null，断开前后半段，然后让后面半段，逆序链表，逆序后的后半段头节点为cur//（3）然后让head后cur对比，相等就没事，一旦不相等，非回文！//（4）对比完成，拿到结果，然后需要将后半段逆序恢复，然后接上前半段，返回结果后，咱不可以破坏链表的原始结构。public static boolean isPalidromeFace(Node head){if (head == null || head.next == null) return true;boolean ans = true;//默认是OK//（1）既然快慢指针可以用来锁定中点，则我们就有办法找到前后各自一半Node fast = head;Node slow = head;while (fast.next != null && fast.next.next != null){fast = fast.next.next;slow = slow.next;}//（2）让slow指针指向null，断开前后半段，然后让后面半段，逆序链表，逆序后的后半段头节点为curNode head2 = slow.next;//后半段头结点slow.next = null;//断开前后//逆序后半段Node pre = null;Node next = head2.next;while (head2 != null){//逆序代码，标准的，next记录head2下次要去的点，让head2回指pre，然后pre去head2，head2去next//直到head2是null停止next = head2.next;head2.next = pre;//逆序pre = head2;head2 = next;}//（3）然后让head后cur对比，相等就没事，一旦不相等，非回文！//此时，pre就是后半段逆序之后的头节点了，咱们让左半段和右半段对比Node cur = head;//左边头head2 = pre;//为了恢复右半段，还得用head2记住这个头节点哦while (cur != null && pre != null){//只要一个结尾了，就不用继续了if (cur.value != pre.value){ans = false;break;//提前结束对比工作}//没事继续留到cur = cur.next;pre = pre.next;}//（4）对比完成，拿到结果，然后需要将后半段逆序恢复，然后接上前半段，返回结果后，咱不可以破坏链表的原始结构。//刚刚咱们用head2记住了右半段的头结点，故可以利用它恢复pre = null;next = null;while (head2 != null){//逆序代码，标准的，next记录head2下次要去的点，让head2回指pre，然后pre去head2，head2去next//直到head2是null停止next = head2.next;head2.next = pre;//逆序pre = head2;head2 = next;}//恢复以后，pre是头结点，我们需要把左半段的slow接到pre上，完成整体挂接slow.next = pre;return ans;//返回结果}
咱们来测试一把：
public static void test2(){Node head = createLinkNode();System.out.println(isPalidrome(head));Node head2 = createLinkNode();System.out.println(isPalidromePen2(head2));Node head3 = createLinkNode();System.out.println(isPalidromeFace(head2));}public static void main(String[] args) {
// test();test2();}
以上三个解决方案，都没问题
true
true
true
总结
提示：重要经验：
1）回文结构的特点，正序=逆序，回文链表，回文串，未来回文串的算法设计，是大放异彩的地方
2）快慢指针找中点，上中点，还有逆序代码，必须要熟悉！
3）笔试求AC,不考试空间复杂度，但是面试不仅要优化时间复杂度，也必须要优化空间复杂度！
