leetcode

0 class Solution {

1 public:

2 ListNode *invert(ListNode *head) {

3 ListNode *p, *q, *r;

4

5 p = head;

6 q = nullptr;

7 while (p) {

8 r = q;

9 q = p;

10 p = p->next;

11 q->next = r;

12 }

13 return q;

14 }

15

16 ListNode *first_half_end(ListNode *head) {

17 ListNode *fast, *slow;

18 fast = slow = head;

19 while (fast->next && fast->next->next) {

20 fast = fast->next->next;

21 slow = slow->next;

22 }

23 return slow;

24 }

25

26 bool isPalindrome(ListNode *head) {

27 if (!head || !head->next) return true;

28

29 ListNode *fhe = first_half_end(head);

30 ListNode *shs = invert(fhe->next);

31

32 for (ListNode *p = head, *tmp = shs; tmp; p = p->next, tmp = tmp->next)

33 if (p->val != tmp->val) return false;

34

35 return true;

36 }

37 };