判断链表是否是回文链表？回文结构，回文串

判断链表是否是回文链表？回文结构，回文串
提示：关于回文结构：是有非常多的互联网大厂的题，也涉及到很重要的算法基础原型，所以要透彻理解！
本文的基础知识点：
找到链表的中点，上中点，或者下中点的知识点：
（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 = http://www.kingceram.com/post/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)的时间复杂度，来遍历确认两两是否相等。故o(N)时间复杂度是绕不过去的
只能在空间上做一些优化，赢得面试官的青睐！！！
笔试求AC,咱可以不考虑空间复杂度，随意做，代码简单就能通过
但是面试，是要最优解，既要考虑时间复杂度，又要考虑空间复杂度。
一点空间都不节约的暴力逆序对比
这很容易，笔试AC可以写的简单代码
将整个链表全部放入栈，然后不断弹出逆序，与原链表对比即可
手撕代码：
【判断链表是否是回文链表？回文结构，回文串】//复习回文结构//（1）一点空间都不节约的暴力逆序对比//这很容易，笔试AC可以写的简单代码//将整个链表全部放入栈，然后不断弹出逆序，与原链表对比即可public static boolean isPalidrome(Node head){if (head == null || head.next == null) return true;Stack 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中，是回文结构，也只需要对比一半
手撕代码：