text: /**
   * Definition for singly-linked list.
   * struct ListNode {
   *     int val;
   *     ListNode *next;
   *     ListNode(int x) : val(x), next(NULL) {}
   * };
   */
  
  
  class Solution {
  public:
      /*
       * @param head: A ListNode.
       * @return: A boolean.
       */
      bool isPalindrome(ListNode * head) {
          // write your code here
          if (head == nullptr || head->next == nullptr) {
              return true;
          }
          
          ListNode* slow = head;
          ListNode* fast = head->next;
          while (fast && fast->next) {
              slow = slow->next;
              fast = fast->next->next;
          }
          
          slow->next = reverseList(slow->next);
          slow = slow->next;
          
          while (slow) {
              if (slow->val != head->val) {
                  return false;
              }
              slow = slow->next;
              head = head->next;
          }
          return true;
      }
      
  private:
      ListNode* reverseList(ListNode* head) {
          if (head == nullptr) {
              return head;
          }
          
          ListNode* curr = head;
          ListNode* prev = nullptr;
          while (curr) {
              ListNode* next = curr->next;
              curr->next = prev;
              prev = curr;
              curr = next;
          }
          return prev;
      }
  };
  