solved 'Palindrome Linked List' on leetcode https://leetcode.com/problems/palindrome-linked-list/

palindrome_linked_list.cc

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head) {
            return true;
        }
        // Get the size of the linked list.
        auto iter = head;
        int sz = 0;
        while (iter) {
            iter = iter->next;
            ++sz;
        }
        
        iter = head;
        for (int i = 0; i < sz / 2; ++i) {
            iter = iter->next;
        }
        
        // Reverse the second half linked list.
        auto tail_iter = reverse(iter);
        // Record the recover point.
        auto recover_point = tail_iter;
        iter = head;
        bool is_palindrome = true;
        for (int i = 0; i < sz / 2; ++i) {
            if (tail_iter->val != iter->val) {
                is_palindrome = false;
                break;
            } else {
                iter = iter->next;
                tail_iter = tail_iter->next;
            }
        }
        // Recover the second half.
        reverse(recover_point);
        return is_palindrome;
    }
private:
    ListNode* reverse(ListNode* head) {
        // `head` cannot be empty.
        auto curr = head, next = curr->next;
        curr->next = nullptr;
        while (next) {
            auto next_next = next->next;
            next->next = curr;
            curr = next;
            next = next_next;
        }
        return curr;
    }
};