Palindrome Linked List

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

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

O(n) time, O(n)space solution, use a stack.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 // assume I can manipulate this linked list
class Solution {
public:
    stack<int> st;
    bool isPalindrome(ListNode* head) {
        int length = getLength(head);
        for(int i = 0; i < length; i++){
            if(i < length / 2){
                st.push(head->val);
            }else if(i == length / 2 && length % 2 == 1){
                ;
            }else{
                if(head->val != st.top()){
                    return false;
                }else{
                    st.pop();
                }
            }
            head = head->next;
        }
        return true;
    }
    int getLength(ListNode * head){
        int count = 0;
        while(head != nullptr){
            count++;
            head = head->next;
        }
        return count;
    }
};

O(1) space solution, reverse the linked list from middle.

Then traverse them together. Compare each node