回文链表

bool isPalindrome(ListNode *head) {
  if (!head->next) return true;
  // 快慢指针定位中点
  auto arr = middle_and_pre(head);
  ListNode *pre_head2 = arr[0];
  ListNode *head2 = reverse(arr[1]);
  bool is_pal = true;
  // 中点反转后对比
  while (head2 != nullptr) {
    if (head->val != head2->val) {
      is_pal = false;
      break;
    }
    head = head->next;
    head2 = head2->next;
  }
  // 复原
  pre_head2->next = reverse(head2);
  return is_pal;
}

// 获取中点和中点的前一个节点
vector<ListNode *> middle_and_pre(ListNode *head) {
  ListNode *slow = head;
  ListNode *fast = head;
  ListNode *pre = nullptr;
  while (fast && fast->next) {
    pre = slow;
    slow = slow->next;
    fast = fast->next->next;
  }
  return {pre, slow};
}

// 反转链表
ListNode *reverse(ListNode *head) {
  ListNode *pre = nullptr;
  ListNode *cur = head;
  while (cur != nullptr) {
    ListNode *nxt = cur->next;
    cur->next = pre;
    pre = cur;
    cur = nxt;
  }
  return pre;
}