package com.javause.Algorithm.isPalindrome;

import java.util.Stack;

import org.junit.Test;

/**

 *  * 一个链表是否是回文结构  *  */ public class ReturnStruct {  class Node {   public int value;   public Node next;

  public Node(int data) {

   this.value = data;   }  }

 /**

  * 方法一：将链表节点依次入栈，入栈完成后，依次出栈，如果可以和原来的链表值对上，那就是回文结构，逆序之后，值相同   *   */  public boolean isPalindromel(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;

 }

 /**

  * 方法二：并不是将所有节点入栈，压入一半节点即可，如果长度为N,N为 偶数，前N/2的节点叫左边区,后N/2的节点叫右半区   * N为奇数,忽略处于最中间的节点，还是前N/2的节点叫左半区，后N/2的节点 叫右半区。   * 把右边部分压入栈中，压入完成后，检查栈顶到栈底的值出现顺序是否和 链表左边的值相互对应   *   */  public 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;  }

 /**

  * 方法三：右半区反转，指向中间节点 将左边区第一个节点记为leftStart，右半区反转后第一个节点记为rightStart   * 1.leftStart和rightStart同时向中间节点移动，移动每一步都比较leftStart和   * rightStart的值，看是否一样，如果都一样，说明为回文结构 2.不管最后是不是回文，都要把链表恢复成原来的结构 3.恢复完成后，返回检查结果   *   */  public 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) // 查找中间节点   {    n1 = n1.next; // 中部n1    n2 = n2.next.next; // n2尾部   }   n2 = n1.next; // n2,右边第一个节点   n1.next = null;// 将中间节点指针断开   Node n3 = null;   while (n2 != null) { // 右半区反转    n3 = n2.next;// n3保存下一个节点    n2.next = n1; // n2指向中间节点    n1 = n2; // n1移动    n2 = n3;// n2移动   }

  n3 = n1;// n3->保存最后一个节点

  n2 = head;// n2->左边第一个节点

  boolean res = true;

  while (n1 != null && n2 != null) {// 检查回文    if (n1.value != n2.value) {     res = false;     break;    }    n1 = n1.next;    n2 = n2.next;   }   n1 = n3.next;   n3.next = null;   while (n1 != null) {// 恢复列表    n2 = n1.next;    n1.next = n3;    n3 = n1;    n1 = n2;   }   return res;  }

 

 public void test() {   Node node1 = new Node(1);   Node node2 = new Node(2);   Node node3 = new Node(2);   Node node4 = new Node(1);   Node node5 = new Node(1);

  node1.next = node2;

  node2.next = node3;   node3.next = node4;   node4.next = node5;

  System.out.println(isPalindromel(node1));

  System.out.println(isPalindrome2(node1));

  System.out.println(isPalindrome3(node1));

 }

}