#include <iostream>
#include <stack>
#include <cassert>
using namespace std;
struct ListNode {
   int val;
   ListNode *next;
   ListNode(int x) : val(x),next(NULL) {}
};
 
//方法一：O(n) time O(n) space,过了
bool isPalindrome(ListNode *head) {
   if (head == NULL)
       return true;
   stack<int> list;
   for (ListNode * temp = head; temp!=NULL; temp = temp->next) {
       list.push(temp->val);
   }

   for (ListNode * temp = head; temp!=NULL; temp = temp->next) {
       if (temp->val != list.top())
           return false;
       list.pop();
   }
   return true;
}
//方法二：既然用到了栈，递归的过程本来就是出入栈的过程。所以可以用递归实现,但由于递归要存中间很多东西，space会超过O(1).O(n) time
class Solution {
private:
   ListNode * list;
   bool judge(ListNode *head) {
       if (head == NULL)
           return true;
       if (judge(head->next) == false)
           return false;
       if (list->val == head->val) {
           list = list->next;
           return true;
       } else {
           return false;
       }
   }
public:

   bool isPalindrome(ListNode *head) {
       if (head == NULL || head->next == NULL)
           return true;
       list = head;
       return judge(head);
   }

};

//方法三：O(n^2) time O(1) space，过了
bool compare(ListNode *head, int left, int right) {
   assert(left<right);
   if (left == 0)
       return true;
   int count=0;
   int leftVal,rightVal;
   for (ListNode * temp = head; temp!=NULL; temp = temp->next) {
       count++;
       if (count == left)
           leftVal = temp->val;
       if (count == right) {
           rightVal = temp->val;
           break;
       }
   }
   if (leftVal != rightVal) {
       return false;
   } else {
       compare(head,left-1,right+1);
   }

}
bool isPalindrome_2(ListNode *head) {
   int ListLength = 0;
   for (ListNode * temp = head; temp!=NULL; temp = temp->next) {
       ListLength ++;
   }
   if (ListLength & 0x01) {
       return compare(head,ListLength/2,ListLength/2+2);
   } else {
       return compare(head,ListLength/2,ListLength/2+1);
   }

}

//方法四，先扫一遍找到中点，逆转前半个链表，一一对比,O(n) time O(1) space

ListNode * reverse(ListNode *head, int end) {
   ListNode *right = head;
   int count = 1;
   while (count < end) {
       right = right -> next;
       count ++;
   }
   ListNode* t = head;
   ListNode* prev(NULL);
   ListNode* endNode = right->next;
   while (t!=endNode) {
       ListNode * n = t->next;
       t->next = prev;
       prev = t;
       t = n;
   }

   return right;
}
bool compare_4(ListNode *head, int end, int start) {

   ListNode *right = head;
   int count = 1;
   while (count < start) {
       right = right -> next;
       count ++;
   }

   //先找到右半边，在reverse左半边，顺序颠倒会出错

   ListNode * left = reverse(head,end);
   while (left!=NULL && right !=NULL && left->val == right->val) {
       left = left -> next;
       right = right -> next;
   }
   if (left == NULL && right ==NULL) {
       return true;
   } else {
       return false;
   }

}
bool isPalindrome_4(ListNode *head) {
   if (head == NULL || head->next == NULL)
       return true;

   int ListLength = 0;
   ListNode * temp = head;
   while(temp) {
       ListLength ++;
       temp = temp->next;
   }
   //找链表的中点，可以用快慢指针法，一个走一步，一个走两步，快的结束，慢得到达中心
   if (ListLength & 0x01) {
       return compare_4(head,ListLength/2,ListLength/2+2);
   } else {
       return compare_4(head,ListLength/2,ListLength/2+1);
   }

}