Problem:

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

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

思路：

Solution (C++):

bool isPalindrome(ListNode* head) {
    if (!head) return true;
    vector<int> nums;
    while (head) {nums.push_back(head->val); head = head->next;}
    int n = nums.size();
    for (int i = 0; i <= n/2; ++i) {
        if (nums[i] != nums[n-1-i])  return false;
    }
    return true;
}

性能：

Runtime: 20 ms  Memory Usage: 11.3 MB

思路：

Solution (C++):

性能：

Runtime: ms  Memory Usage: MB