题目：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
- 给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
- 测试样例：1->2->2->1
- 返回：true
方法1：
空间O(n)整个链表遍历两边， 开一个栈，第一遍遍历把链表中每个元素push进栈中，
这样堆中的元素的pop顺序就是链表的倒序输出；第二遍就开始pop栈中数据，每pop一个数据，
就把这个数据跟链表中进行对比，如果相同继续往下走，如果不同返回false。
此种情况下，时间复杂度为O(n)，空间复杂度为O(n)。
/**
* 思路1：空间O(n)整个链表遍历两边， 开一个栈，第一遍遍历把链表中每个元素push进栈中，
* 这样堆中的元素的pop顺序就是链表的倒序输出；第二遍就开始pop栈中数据，每pop一个数据，
* 就把这个数据跟链表中进行对比，如果相同继续往下走，如果不同返回false。
* 此种情况下，时间复杂度为O(n)，空间复杂度为O(n)。
* @param head
* @return
*/
public static boolean chkPalindrome1(Node head) {
Stack<Node> stack = new Stack<>();
Node headTemp = head;
while (head != null) {
stack.push(head);
head = head.next;
}
while (headTemp != null && !stack.empty()) {
if (headTemp.value == stack.pop().value) {
headTemp = headTemp.next;
} else {
return false;
}
}
return true;
}
方法2：
分别正序和逆序拼接节点值字符串， 比较字符串是否相同
时间复杂度为O(n)，空间复杂度为O(1)
/**
* 分别正序和逆序拼接节点值字符串， 比较字符串是否相同
* 时间复杂度为O(n)，空间复杂度为O(1)
* @param head
* @return
*/
public static boolean chkPalindrome2(Node head) {
String str1 = ""; //正序拼接
String str2 = ""; //逆序拼接
while (head != null) {
str1 = str1 + head.value;
str2 = head.value + str2;
head = head.next;
}
if(str1.equals(str2) && str1.length() > 1){
return true;
}
return false;
}
方法3：
1 找到链表中点，
2 翻转右半部分，
3 从两个链表头开始判断节点值相同。
4 然后再将右侧链表翻转回来
复杂度: 时间O(n), 空间O(1)
/**
* 1 找到链表中点，
* 2 翻转右半部分，
* 3 从两个链表头开始判断节点值相同。
* 4 然后再将右侧链表翻转回来
*
* 复杂度
* 时间O(n) 空间O(1)
*
* @param head
* @return
*/
public static boolean chkPalindrome3(Node head) {
//找到中点
Node mid=head;//中点
Node fast=head;
while(fast.next!=null&&fast.next.next!=null) {//奇偶长度情况
fast=fast.next.next;
mid=mid.next;
}
//翻转右侧链表
Node cur=mid.next;//
mid.next=null;
Node behind = null;
Node before = mid;//右侧翻转后尾节点指向中间节点，中间节点为左右两个链表的共同尾节点
while(cur!=null) {
behind=cur.next;
cur.next=before;
before=cur;
cur=behind;
}
Node rHead=before;
//检查是否是回文的
Node lNode=head;
Node rNode=before;//
boolean res=true;
while(lNode!=null && rNode!=null) {//原链奇偶长度都ok, 某一半最早到null，就结束比较了
System.out.println("左：" + lNode.value + ", 右： " + rNode.value);
if(lNode.value!= rNode.value) {
res=false;
break;
}
lNode=lNode.next;
rNode=rNode.next;
}
//右侧链表翻转回去
before=rHead;
cur=rHead.next;
behind=null;
while(cur!=null) {
behind=cur.next;
cur.next=before;
before=cur;
cur=behind;
}
return res;
}
测试：
public static void main(String[] args) {
Node n1=new Node(1);
Node n2=new Node(2);
Node n3=new Node(3);
Node n4=new Node(3);
Node n5=new Node(2);
Node n6=new Node(1);
n1.next=n2;
n2.next=n3;
n3.next=n4;
n4.next=n5;
n5.next=n6;
Node head=n1;
boolean result= chkPalindrome3(head);
System.out.println(result);
}
