Given the head of a singly linked list, return true if it is a palindrome.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

The number of nodes in the list is in the range [1, 10^5].
0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

Solution

Time complexity : O(n)
Space complexity : O(1)

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *firstEnd = endOfFirstHalf(head);
        ListNode *revSecHalf = reverseList(firstEnd->next);
        
        ListNode *p1 = head, *p2 = revSecHalf;
        bool ans = true;
        while (ans && p2 != nullptr) {
            if (p1->val != p2->val) ans = false;
            p1 = p1->next;
            p2 = p2->next;
        }
        firstEnd->next = reverseList(firstEnd->next);
        return ans;
    }
private:
    ListNode* endOfFirstHalf(ListNode *head) {
        ListNode *f, *s;
        f = s = head;
        while (f->next && f->next->next) {
            f = f->next->next;
            s = s->next;
        }
        return s;
    }
    
    ListNode* reverseList(ListNode *head) {
        ListNode *prev = nullptr;
        ListNode *curr = head;
        while (curr) {
            ListNode *tmpNext = curr->next;
            curr->next = prev;
            prev = curr;
            curr = tmpNext;
        }
        return prev;
    }
};

用快慢指標找到前半段的結尾。
將後半段反轉。
逐一比對。
恢復反轉。
返回結果。