2.7 --- check if a list is palindrome

Q:
Implement a function to check if a linked list is a palindrome.

A：
Solution #1: reverse and compare
Idea： create another list reversely , and compare two list  (注意，我们只需要对比前一半儿就行了。 也就是说，创建新的list的时候，计数得知listSize）

 private static boolean checkPalindrome(LinkList list) {
  // create another list reversely , and compare them one by one
  LinkList newList = new LinkList();
  Node runner = list.header.next;
  while (runner != null) {
   Node tmpNode = new Node(runner.data);
   newList.insertAtBeginning(tmpNode);

   runner = runner.next;
  }
  // compare the two list
  Node runner1 = list.header.next;
  Node runner2 = newList.header.next;
  while (runner1 != null && runner2 != null && runner1.data == runner2.data) {
   runner1 = runner1.next;
   runner2 = runner2.next;
  }
  if (runner1 == null && runner2 == null) { // reach the end of these two
             // list
   return true;
  } else {
   return false;
  }

 }

Solution #2: Iterative Approcach
 use a stack to store the first half part.
1) if the list size is already known, delete the size,  (be careful of when the list size is odd.
2) if the list size is unknown.  use a fast/ slow runner, when the fast reach end, slow only at middle, 

 private static boolean checkPalindrome(LinkList list) {
  // create another list reversely , and compare them one by one
  Node slowRunner = list.header;
  Node fastRunner = list.header;
  // in math, fastRunner point to the node: 2,4,6,8
  // slow point to the 1,3,5,7
  while (fastRunner != null && fastRunner.next != null) {
   fastRunner = fastRunner.next.next;
   slowRunner = slowRunner.next;

  }
  boolean isListSizeOdd = false; // default is Even number
  if (fastRunner == null) {// list length is odd number
   // Now slowRunner point to exactly the middle one
   isListSizeOdd = true;
  }

  fastRunner = list.header.next;
  // put into Stack
  Stack stack = new Stack();
  if (isListSizeOdd) {
   while (fastRunner != slowRunner) {
    stack.push(fastRunner);
    fastRunner = fastRunner.next;
   }
  } else { // list length is even number, the slowRunner point to the
   while (fastRunner != slowRunner.next) {
    stack.push(fastRunner);
    fastRunner = fastRunner.next;
   }
  }
  slowRunner = slowRunner.next; // slowRunner point to the half tail part.
  while (slowRunner != null && !stack.isEmpty()) {
   Node tmpNode = stack.pop();
   if (tmpNode.data != slowRunner.data) {
    return false;
   } else {
    slowRunner = slowRunner.next;
   }

  }
  if (slowRunner == null & stack.isEmpty()) {
   return true;
  } else {
   System.err.println("something wrong");
   System.exit(1);
   return false;
  }

 }

这里犯了一个错误，就是由于 边想边写，头脑不够清晰。 导致判断的时候，有混淆。
以后写这种代码的时候，要先想清楚了，在纸上写好了，再誊到eclipse上

Solution #3: Recursive Approcach

要recursively 建立一个前后匹配的对儿。然后，逐层缩简。









Mistakes: 
1: 两个runner， 刚开始用了runner1.equals(runner2). 但是，其实二者是不同的list里的对象。 不能这样搞的。