判断一个链表是否为回文结构

题目：给定一个链表的头结点head，判断该链表是否为回文结构

例如： 1->2->1 ,true 1->2->2->1, true 1->2->3, false

使用栈来解决

最直接的想法应该就是利用栈来解决这个问题了。 判断回文结构的最核心思想： 从左到右读的顺序和从右到左读的顺序是一样的，这实际上暗示了使用栈，因为如果压栈序列和出栈序列是一样的，那么这就肯定是一个回文结构了！

//此处定义的Node类，应该是在一个Node.java文件中。 //或者是在一个类中作为内部类存在。 public class Node{ public int val; public Node next; public Node(int val){ this.val=val; this.next=next; } } //回文方法 public boolean isPalindrome1(Node head){ Stack<Node> stack=new Stack<Node>(); Node cur=head; while(cur!=null){ stack.push(cur); cur=cur.next; } while(!stack.empty()){ // Node tmp=stack.pop(); if(tmp.val==head.val){ head=head.next; } else{ return false; } } return true; }

判断一半即可

还有更好的方法，也是利用栈结构，但是其实我们只需要压入链表的一半到栈中即可。 假设链表的长度为N，如果N是偶数，前N/2的节点称为左半区，后N/2的节点称为右半区；如果N是奇数，除去中间的节点，仍然是前N/2为左半区，后N/2为右半区。 链表:1->2->2->1 , 对应左半区 1,2 右半区：2，1

核心： 检查右半区压入栈后，从栈顶到栈底的顺序是否和左半区的顺序一样。 将链表右半部分存入栈是通过折叠的方法！ 实际上还是利用了快慢指针来找到链表的中间位置！

public boolean isPalindrome2(Node head){ if(head==null|head.next==null) return true; Node right=head.next; Node cur=head; while(cur.next!=null&&cur.next.next!=null){ right=right.next; cur=cur.next.next; } Stack<Node> stack=new Stack<Node>(); while(right!=null){ stack.push(right); right=right.next; } while(!stack.empty()){ if(stack.pop().val!=head.val) return false; head=head.next; } return true; }

进阶，不需要栈，且O（N）时间复杂度

步骤：

改变链表的右半区的结构，反转整个右半区链表，让它最后指向中间节点。左半区第一个节点记为leftStart，右半区反转后的头节点记为rightStartleftStart和rightStart同时向中间点移动，移动每一步都比较leftStart和rightStart的值，如果都一样则为回文结构否则不是不管true还是false，恢复链表链表恢复之后返回结果。

核心：利用快慢指针找到中间点，反转链表的基本方法（申请多一个结点暂存）

public boolean isPalindrome3(Node head){ if(head==null||head.next==null) return true; Node n1=head;//存中间位置 Node n2=head; //找到中间节点 while(n2.next!=null&&n2.next.next!=null){ n1=n1.next; n2=n2.next.next; } n2=n1.next;//右半部分第一个节点 n1.next=null; Node n3; //反转右半区 while(n2!=null){ n3=n2.next; //暂存n2下一个节点 n2.next=n1;//反转 n1=n2;//移动n1 n2=n3;//移动n2 } n3=n2;//n3保存最后一个节点,其实也就是现在的右半区的第一个节点,n3始终是优先考虑作为一个暂存节点 n2=head;//n2存左半区第一个节点 boolean res=true; while(n1!=null&&n2!=null){ if(n1.val!=n2.val) { res=false; break; } n1=n1.next; n2=n2.next; } n1=n3.next;//n1存n3的下一个节点，即原链表中的倒数第二个节点。 n3.next=null;//最后一个节点的下一个应该是null //恢复 while(n1!=null){ n2=n1.next;//暂存 n1.next=n3; n3=n1; n1=n2; } return res; }