palindrome-linked-list-lcci，回文链表题目，力扣解法,首先我们使用非常直观的解题方法。

平平无奇 空间O(n)复杂度

/**
 * 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) {
        vector<int> res;
        while(head)
        {
            res.push_back(head->val);
            head = head->next;
        }

        for(int i = 0;i < res.size()/2;i++)
        {
            if(res[i] != res[res.size() - 1 - i]) return false;
        }

        return true;
    }
};

运行效率:

执行结果：通过  显示详情
执行用时：20 ms, 在所有 C++ 提交中击败了 84.98% 的用户
内存消耗：14 MB, 在所有 C++ 提交中击败了 48.79% 的用户

递归

我们使用指针positive_pointer记录一个全局的正向链表结构，使用递归，每次判断正向和逆向对应的元素是否相同。实际上使用递归，这里的空间复杂度依然是O(N)。函数调用是一个压栈 出栈的过程，存在一定的性能开销，我们可以从运行效率看出来，这个方法实际上也不比第一个方法快。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
private:
    bool recursivelyCheck(ListNode * currentNode) {
        if(currentNode)
        {
            if(!recursivelyCheck(currentNode->next))
                return false;
            
            if(currentNode->val != positive_pointer->val)
                return false;
            
            positive_pointer = positive_pointer->next;
        }

        return true;
    }
public:
    bool isPalindrome(ListNode* head) {
        positive_pointer = head;
        return recursivelyCheck(head);
    }
private:
    ListNode* positive_pointer;
};

O(1)空间复杂度

O(1)空间复杂度，需要将后半段逆序，然后进行比较，这种方法的弊端是修改了链表。

/**
 * 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 == nullptr)
            return true;
        ListNode *first_end = endOfFirstHalf(head);
        ListNode *second_start = reverseList(first_end->next);
        while(second_start)
        {
            if(head->val != second_start->val)
                return false;
            second_start = second_start->next;
            head = head->next;
        }

        return true;
    }

private:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    ListNode* endOfFirstHalf(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};