链表面试题之判断是否为回文链表—三种方式解决，总有一种方法让面试官满意
座右铭：代码虐我千百遍，我待代码如初恋！！！
给定一个单链表的头节点head，请判断该链表是否为回文结构。
- 栈方法特别简单（笔试用)
- 改原链表的方法就需要注意边界了（面试用）
第一种方法：用一个栈来辅助实现，将链表从头结点开始依次压入栈中，之后再从栈顶依次弹出并与原链表一个一个进行比较，，如果相比较的过程全部相同，说明是回文结构，如果有一个比对不上就不是回文结构。因为栈的特征是先进后出的，所以弹出的过程就是逆序的过程。这个方法比较简单，缺点就是费点空间，需要O(N)的空间复杂度
第二中方法：第一种基础上改进一下，同样需要一个栈来辅助实现，但是只需要用到栈的一半空间，所以空间复杂度为O(N/2)。额外申请两个变量，一个快指针和慢指针。让慢指针指向链表右半部分的第一个结点，然后将右半部分压入栈中，再从栈中弹出和左半部分一一比较
第三中方法：不用申请栈，只需要O(1)的空间复杂度。申请一个快指针和慢指针，链表结点个数为奇数的时候慢指针来到中点位置，；偶数个的时候，慢指针来到上中点位置。然后将右半部分链表反转，慢指针指向的结点指向空。此时再让慢指针和快指针分别从最右边和最左边开始一一进行比较。最后返回结果之前一定要将右半部分链表反转回来！！！此方法难点在于难抠边界，但是是最优解，适合面试的时候和面试官聊聊哈哈哈~~~///(v)\~~~
package com.harrison.class06;
import java.util.Stack;
public class Code02_IsPalindromeList {
public static class Node {
public int value;
public Node next;
public Node(int v) {
value = v;
}
}
// need n extra space
public static boolean isPalindrome1(Node head) {
Stack<Node> stack = new Stack<Node>();
Node cur = head;
// 将链表从头结点开始依次压入栈中
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
// 从栈顶依次弹出和链表开始比较
while (head != null) {
if (head.value != stack.pop().value) {
return false;
}
head = head.next;
}
return true;
}
// need n/2 extra space
public static 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;
}
// right 奇数个来到中点位置 偶数个来到下中点位置
Stack<Node> stack = new Stack<>();
// 链表的右半部分依次压入栈中
while (right != null) {
stack.push(right);
right = right.next;
}
// 从栈中依次弹出 和链表左部分依次比较
while (!stack.isEmpty()) {
if (head.value != stack.pop().value) {
return false;
}
head = head.next;
}
return true;
}
// need O(1) extra space
public static boolean isPalindrome3(Node head) {
if (head == null || head.next == null) {
return true;
}
Node n1 = head;// 慢指针 n1 -> mid
Node n2 = head;// 快指针 n2 -> end
while (n2.next != null && n2.next.next != null) {
n1 = n1.next;
n2 = n2.next.next;
}
// 慢指针来到中点或者上中点位置 快指针来到终点
n2 = n1.next;// n2 来到右部分第一个结点
n1.next = null;// n1.next -> null
Node n3 = null;
// 右部分反转
while (n2 != null) {
n3 = n2.next;// n3 -> save next node
n2.next = n1;// next of right node convert
n1 = n2;// n1 move
n2 = n3;// n2 move
}
n3 = n1;// n3 -> save last node
n2 = head;// n2 -> left first node
boolean res = true;
// 慢指针从右边开始 快指针从头结点开始 一一比较，任何一个为空就停下来
while (n1 != null && n2 != null) {
if (n1.value != n2.value) {
res = false;
break;
}
n1 = n1.next;// left to mid
n2 = n2.next;// right to mid
}
n1 = n3.next;
n3.next = null;
// 将右部分逆序回来
while (n1 != null) {
n2 = n1.next;
n1.next = n3;
n3 = n1;
n1 = n2;
}
return res;
}
public static void printLinkedList(Node head) {
System.out.print("Linked List:");
while (head != null) {
System.out.print(head.value + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = null;
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(2);
head.next.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(2);
head.next.next.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
}
}