座右铭：代码虐我千百遍，我待代码如初恋！！！
给定一个单链表的头节点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("========================="); } }
