1
class Solution {
2
 public:
3
  ListNode *reverse(ListNode *head) {
4
    ListNode *prev = nullptr;
5
    while (head) {
6
      ListNode *current = head->next;
7
      head->next = prev;
8
      prev = head;
9
      head = current;
10
    }
11
    return prev;
12
  }
13
  bool isPalindrome(ListNode *head) {
14
    if (!head || !head->next) return true;
15
    ListNode *tort = head;
16
    ListNode *hare = head;
17
    while (hare->next && hare->next->next) {
18
      tort = tort->next;
19
      hare = hare->next->next;
20
    }
21
    tort->next = reverse(tort->next);
22
    tort = tort->next;
23
    ListNode *dummy = head;
24
    while (tort) {
25
      if (tort->val != dummy->val) return false;
26
      tort = tort->next;
27
      dummy = dummy->next;
28
    }
29
    return true;
30
  }
31
};
32

33
Time Complexity : O(n / 2) + O(n / 2) + O(n / 2) Space Complexity : O(1)