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

链表2：判断一个链表是否为回文结构"/>

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

【题目】 给定一个链表的头节点head，请判断该链表是否为回 文结构。 例如： 1->2->1，返回true。 1->2->2->1，返回true。 15->6->15，返回true。 1->2->3，返回false。
进阶： 如果链表长度为N，时间复杂度达到O(N)，额外空间复杂 度达到O(1)。
思想：这里介绍三种方法：
1，把链表中的数据全部放在栈里面，然后依次比对。
2，定义一个快指针，一个慢指针，然后把链表折中，把后面的部分压入到栈里，再比对。
3，不用辅助空间，慢指针走一步，快指针走两步，当慢指针走到中点时，快指针走到终点了，把后半部分逆序，再从开头各走一步比较。看图理解：

几种方法的代码：

package class_03;import java.util.Stack;public class Code_11_IsPalindromeList {public static class Node {public int value;public Node next;public Node(int data) {this.value = data;}}// 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 spacepublic 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;}Stack<Node> stack = new Stack<Node>();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 spacepublic static 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) { // find mid noden1 = n1.next; // n1 -> midn2 = n2.next.next; // n2 -> end}n2 = n1.next; // n2 -> right part first noden1.next = null; // mid.next -> nullNode n3 = null;while (n2 != null) { // right part convertn3 = n2.next; // n3 -> save next noden2.next = n1; // next of right node convertn1 = n2; // n1 moven2 = n3; // n2 move}n3 = n1; // n3 -> save last noden2 = head;// n2 -> left first nodeboolean res = true;while (n1 != null && n2 != null) { // check palindromeif (n1.value != n2.value) {res = false;break;}n1 = n1.next; // left to midn2 = n2.next; // right to mid}n1 = n3.next;n3.next = null;while (n1 != null) { // recover listn2 = n1.next;n1.next = n3;n3 = n1;n1 = n2;}return res;}public static void printLinkedList(Node node) {System.out.print("Linked List: ");while (node != null) {System.out.print(node.value + " ");node = node.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("=========================");}}