判断回文链表【两种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;}
};
执行结果:
可以看到,降低了近一半的执行用时,但和列表相比还是耗费了大量用时。