//234. 回文链表
/*
可以使用栈等方法，但是题目说最好不要使用额外的空间
1、容易理解的方法：
  先使用双指针找到中间节点：第一个while
  然后将前半部分链表翻转：第二个while
  最后使用双指针同时遍历两部分链表：第三个while
2、可能更快一点，但是比较复杂的方法：
  在找中间节点的同时，将前半部分链表翻转
  最后同时遍历
*/
class Solution {
public:
  bool isPalindrome(ListNode* head) {
    ListNode* p = head;
    ListNode* q = head;
    int num = 0;
    while (q != NULL) {
      q = q->next; num++;
      if (q == NULL) break;
      p = p->next;
      q = q->next; num++;
    }
    if (num < 2) return true;
    ListNode* l = NULL;
    ListNode* r = p;
    p = head;
    while (p != r) {
      q = p;
      p = p->next;
      q->next = l;
      l = q;
    }
    if (num & 1) r = r->next;
    while (l != NULL) {
      if (l->val != r->val) return false;
      l = l->next;
      r = r->next;
    }
    return true;
  }
};