题目描述:
请判断一个链表是否为回文链表。
难度easy
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
- 题解给出的是反转后半部分链表,然后比较,最后恢复的方法。。。这样把空间复杂度降到了O(1)
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路:
把链表中的数值复制到数组中,然后用双指针,头尾比较即可
时间复杂度O(n),空间复杂度O(n)
代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
vector<int> tmp;
public:
// 把序列的数字记录下来? O(n)空间复杂度 O(n)时间复杂度
bool isPalindrome(ListNode* head) {
ListNode* p = head;
while (p != nullptr) {
tmp.push_back(p->val);
p = p->next;
}
int size = (int)tmp.size();
int k = size/2;
for (int i = 0; i < k; ++i) {
if (tmp[i] != tmp[size-1-i]) {
return false;
}
}
return true;
}
};
Comments | 0 条评论