所谓回文结构，就是链表的正序和反序完全一致。 如：{1}。{1，1}，{1,2,2,1}，{1,2,3,2,1} 这种就认为是回文结构。
当然还有一种限制，认为{1}，和{1,2,3,2,1} 不是回文的。这个主要是判断长度是的奇偶性了，在这里不考虑这个玩意。
为什么不能直接翻转整个链表然后两个链表进行对比呢？ 其实是两个链表上逻辑概念，但是操作的是同一个对象，所以翻转后原始head对象的next就是是空了。所以不能直接翻转整个链表。
正文
那么就开整。还是先定义数据结构。
public class ListNode {
int val;
ListNode next = null;
public ListNode(int val) {
this.val = val;
}
}
生成回文数据：
public static void main(String[] args) {
int[] arrays = {1, 2, 3, 2, 1, 0};
ListNode head = new ListNode(0);
ListNode next = head;
for (int i = 0; i < arrays.length; i++) {
ListNode node = new ListNode(arrays[i]);
next.next = node;
next = node;
}
ListNode showParent = head;
while (showParent != null) {
System.out.println(showParent.val);
showParent = showParent.next;
}
System.out.println("--------------" + palindromic(head));
}
将值添加到一个数组中，然后翻转值数组进行对比
我们判断是否是回文，是通过var 的值进行判断的。那么我们就可以直接将值取出来进行判断。
- 将数据读取到一个集合中。
- 将集合拷贝成一个新的集合。
- 新集合翻转。
- 循环从0开始对比两个集合的值。
private static boolean palindromic(ListNode head) {
ArrayList<Integer> nodes=new ArrayList<>();
while (head!=null){
nodes.add(head.val);
head=head.next;
}
ArrayList<Integer> temp;
temp= (ArrayList<Integer>) nodes.clone();
// 翻转
Collections.reverse(temp);
for (int i=0;i<nodes.size();i++){
if (!Objects.equals(nodes.get(i), temp.get(i))){
return false;
}
}
return true;
}
这种写法的时间复杂度和空间复杂度都是O(n)。
还是借助数组双指针
思路还是将值添加到一个数组里面，但是我们不对数据进行拷贝和翻转。 我直接通过头尾的对比，如果相同就是回文结构。
- 将链表数据添加到一个集合中。
- 直接循环这个集合，定义两个变量，一个从0开始，一个从最后一个开始。两个变量进行对比。
private static boolean palindromic(ListNode head) {
ArrayList<Integer> nodes = new ArrayList<>();
while (head != null) {
nodes.add(head.val);
head = head.next;
}
int left = 0;
int right = nodes.size() - 1;
while (left<=right){
if (!Objects.equals(nodes.get(left), nodes.get(right))){
return false;
}else {
left++;
right--;
}
}
return true;
}
这种写法明显比第一种写法更好，减少了一个拷贝和翻转。但是时间复杂度和空间复杂度还是O(n)。
通过栈的特性，将值压栈做翻转
private static boolean palindromic(ListNode head) {
ListNode old=head;
Stack<Integer> nodes = new Stack<>();
while (head != null) {
nodes.push(head.val);
head = head.next;
}
while (!nodes.isEmpty()){
if (nodes.pop()!=old.val){
return false;
}else {
old=old.next;
}
}
return true;
}
这种写法，直接又减少了两个变量。但是他的空间复杂度和时间复杂度还是O(n)。
长度法找中点
思路是：
- 先计算整个链表的总长度。
- 总长度除以2,比如说是奇数5，翻转后的长度其实是3个，所以我们需要通过翻转后的节点作为循环到条件。
- 翻转后续部分。
- 循环翻转后的链表，并判断是否相同。
private static boolean palindromic(ListNode head) {
// 找到链表的中间节点。
ListNode p=head;
int n=0;
while (p!=null){
n++;
p=p.next;
}
n=n/2;
p=head;
while (n>0){
p=p.next;
n--;
}
// 这个时候的P就是中间节点。
p=reverse(p);
ListNode q=head;
while (p!=null){
System.out.println("p="+p.val+" q="+q.val);
if (p.val!=q.val){
return false;
}else {
p=p.next;
q=q.next;
}
}
return true;
}
private static ListNode reverse(ListNode head) {
ListNode prev=null;
while (head!=null){
ListNode next=head.next;
head.next=prev;
prev=head;
head=next;
}
return prev;
}
这种写法的空间复杂度是O(1),时间复杂度是O(n)。
双指针找中点法
思路，快指针每次走2步，慢指针每次走一步，当快指针走到链表最后的时候，慢指针刚好走到一半。
private static boolean palindromic(ListNode head) {
// 找到链表的中间节点。
ListNode p=head;
ListNode fast=head;
while (fast!=null&&fast.next!=null){
fast=fast.next.next;
p=p.next;
}
// 这个时候的P就是中间节点。
p=reverse(p);
ListNode q=head;
while (p!=null){
System.out.println("p="+p.val+" q="+q.val);
if (p.val!=q.val){
return false;
}else {
p=p.next;
q=q.next;
}
}
return true;
}
private static ListNode reverse(ListNode head) {
System.out.println("---:"+head.val);
ListNode prev=null;
while (head!=null){
ListNode next=head.next;
head.next=prev;
prev=head;
head=next;
}
return prev;
}
这种写法的空间复杂度是O(1),时间复杂度是O(n).和通过长度取中间值对比，首先是减少了查找p节点的循环代码， 同时开始的循环也只有完整循环到一半左右。
