判断回文链表【两种O(n)时间复杂度】

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
LeetCode链接：https://leetcode.cn/problems/palindrome-linked-list

思路一、使用数组辅助存储

        链表的难点在于无法获取前一个元素，因此可以考虑将前半部分的元素使用数组进行存储，然后逆序和链表进行比较。基于以上思路，可以得到以下代码：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        int length = 0;
        ListNode* tmp = head;
        while(tmp){
            length++;
            tmp = tmp->next;
        }
        vector<int> halfList(length / 2);
        tmp = head;

        for (int i = 0; i < length / 2; i++) {
            halfList[i] = head->val;
            head = head->next;
        }
        if(1 == length%2){
            head = head->next;
        }
        for (int i = (length + 1) / 2; i < length; i++) {
            if (head->val != halfList[length - i -1])
                return false;
            head = head->next;
        }
        return true;
    }
};

执行结果：

思路二、使用栈和递归

        回文链表最重要的是判断两端是否相等，一段在头，一段在尾，这种方式完美适配队列和栈，因此可以将元素值分别压入队列和栈，然后进行判断。根据以上思路可以得到以下代码：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<int> valStack;
        queue<int> valQueue;

        while (head) {
            valStack.push(head->val);
            valQueue.push(head->val);
            head = head->next;
        }

        while (!valStack.empty()) {
            if (valQueue.front() != valStack.top())
                return false;
            valQueue.pop();
            valStack.pop();
        }

        return true;
    }
};

执行结果：

关于代码执行时间的思考

        两种算法都是O(n)级别的时间复杂度，执行时间应该相仿，但是可以明显看出，使用队列和栈的方法明显慢于使用列表的方法，这可能是因为队列和栈中有大量的出入栈、出入队列操作，而且列表中使用了提前结束，但是队列和栈中则是进行了全部遍历。为此，在队列中加入长度计数器，提前终止减少出队列、出栈的操作次数。得到了以下改进后的思路二代码：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        int length = 0;
        stack<int> valStack;
        queue<int> valQueue;

        while (head) {
            valStack.push(head->val);
            valQueue.push(head->val);
            head = head->next;
            length++;
        }

		//改为使用长度进行判断
        for (int i = 0; i < length / 2; i++) {
            if (valQueue.front() != valStack.top())
                return false;
            valQueue.pop();
            valStack.pop();
        }

        return true;
    }
};

执行结果：

        可以看到，降低了近一半的执行用时，但和列表相比还是耗费了大量用时。