回文链表
题目描述
思路
方法一：迭代
一个比较自然的想法是，设置两个指针，分别从头尾向中间移动，在移动时比较每个节点的值是否相同。如果不相同，则不是回文链表。在实际实现时，首先遍历整个链表，将每个节点的值复制到一个新的数组中。
这个想法的时间复杂度是$O(n) + O(n) = O(2n)~O(n)$，其中$n$是链表的长度。空间复杂度为$O(n)$。
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> vals;
// 先遍历把所有值取出来，存入新的数组
while(head != nullptr) {
vals.emplace_back(head->val);
head = head->next;
}
for(int i = 0, j = int(vals.size() - 1); i < j; i++, j--) {
if(vals[i] != vals[j]) return false;
}
return true;
}
};
方法二：快慢指针
这里直接参考leetcode官方题解：
也可以看这个视频：【力扣 Leetcode｜234 回文链表Palindrome｜快慢指针
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == nullptr) {
return true;
}
// 找到前半部分链表的尾节点并反转后半部分链表
ListNode* firstHalfEnd = endOfFirstHalf(head);
ListNode* secondHalfStart = reverseList(firstHalfEnd->next);
// 判断是否回文
ListNode* p1 = head;
ListNode* p2 = secondHalfStart;
bool result = true;
while (result && p2 != nullptr) {
if (p1->val != p2->val) {
result = false;
}
p1 = p1->next;
p2 = p2->next;
}
// 还原链表并返回结果
firstHalfEnd->next = reverseList(secondHalfStart);
return result;
}
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
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;
}
};
文档信息
- 本文作者：焦逸凡
- 本文链接：https://ailovejinx.github.io/wiki/leetcode234/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）