什么是回文结构：链表正向和反向看是一样的。例如：1-->2-->2-->1,1-->2-->3-->2-->1这样的链表具有回文结构。1、额外空间复杂度为O(1)：(1)求链表的中点（如果有偶数节点，则求中点）(2)调整链表结构，例如：1-->2-->3-->3-->2-->1，调整为：1-->2-->3<--3<--2<--1，上中点3的下一个节点isnull(3)判断是否为回文结构(4)调整链表为原始结构(5)返回结果/***@authorJava与算法学习：Monday*/publicstaticclassNode{publicint价值;下一个公共节点；公共节点(intv){值=v;}}/***额外的空间复杂度为O(1)**整个过程只使用了三个有限变量n1,n2,n3*/publicstaticbooleanisPalindromeList(Nodehead){//一个链表只有一个节点必须是回文if(head==null||head.next==null){returntrue;}//1.找到这个链表的中点（如果有偶数个节点，找到中点）Noden1=head;节点n2=头；while(n2.next!=null&&n2.next.next!=null){n1=n1.next;n2=n2.next.next;}//此时n1为中点（偶数个节点为上中点）//2.调整链表结构//例如：1-->2-->3-->3-->2-->1，调整为：1-->2-->3<--3<--2<--1，上中点3的下一个节点为null//n2改为第一个右半部分节点n2=n1.next;//将中点（或上中点）的下一个节点设置为空n1.next=无效的;节点n3=null；while(n2!=null){//记录此时右半边节点的下一个节点n3=n2.next;//将n2的下一个节点指向上一个节点n2.next=n1;//调整n1，即在n1之后移动一个节点n1=n2;//调整n2，即n2为原n2的下一个节点n2=n3;}//此时n1为链表的最后一个节点，n2和n3均为null//3.判断是否为回文结构//记录链表的最后一个节点。判断是否为回文结构，调整回链表后，n3=n1；//n2从左边第一个节点开始，n1从最后一个节点开始n2=head;//记录是否为回文booleanres=true;while(n1!=null&&n2!=null){if(n1.value!=n2.value){res=false;//不能直接返回是否是回文结构，还需要调整链表到原来的结构break;}//n1和n2都向中间移动n1=n1.next;n2=n2.下一个；}//4.调整链表为原来的结构n1=n3.next;//链表的最后一个节点指向nulln3.next=null;while(n1!=null){//记录下一个节点n2=n1.next;//n1的下一个节点指向下一个节点（即链表调整为原来的结构）n1.next=n3;//n3向前移动n3=n1;//n1向前移动n1=n2;}//调整后返回最终结果returnres;}2.额外的空间复杂度为O(N)：(1)将链表的元素放入栈中，因为栈是先进后出的，相当于翻转了链表(2)从原链表的头节点开始，与从栈中弹出的元素逐一比较(3)每次值相等，则为回文结构/***以栈为对数**额外空间复杂度为O(N)**@authorJava和算法学习：Monday*/publicstaticbooleancomparator(Nodehead){Stack
