234. Palindrome Linked List

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

思路：

保存一个栈，然后将链表中的结点压入栈中。压完后，依次比较链表节点与栈顶的值是否相等，若不等，返回false，若相等，链表节点右移，栈顶弹出，继续比较。若栈空，则说明是回文链表，返回true。

Solution (C++):

bool isPalindrome(ListNode* head) {
    stack<ListNode*> stk;
    ListNode* tmp = head;
    while (tmp) {
        stk.push(tmp);
        tmp = tmp->next;
    }
    while (!stk.empty()) {
        if (stk.top()->val != head->val)  return false;
        stk.pop();
        head = head->next;
    }
    return true;
}

性能：

Runtime: 24 ms  Memory Usage: 11.5 MB