题目描述
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
1
2
| 输入：head = [1,2,2,1]
输出：true
|
具体见题目描述
算法思路
这道题想要时间复杂度O(n)是很简单的，我写了双指针和反转数组两种方法，感觉效率都还说的过去，但是空间上不行，首先看一下反转数组：
方法一：反转数组
这个很容易理解，直接把链表的值读进一个数组，再把数组倒序，如果$list = reverse(list)$，那么很容易知道这是回文的，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> val_vector;
ListNode *tmp = head;
if (tmp == nullptr) {
return true;
}
while (tmp != nullptr) {
val_vector.push_back(tmp->val);
tmp = tmp->next;
}
vector<int> tmp_vector(val_vector.size());
copy(val_vector.begin(), val_vector.end(), tmp_vector.begin());
reverse(val_vector.begin(), val_vector.end());
if (val_vector == tmp_vector) {
return true;
}
return false;
}
};
|
很容易看出来，空间消耗非常大，用了两个vector去存储中间结果，因此毫无疑问的空间占用大：
方法二：双指针
用两个指针分别指向这个链表的头和尾，同时向中间移动，如果每次$front->val = end->val$都成立，那么毫无疑问这是回文的，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> val_vector;
ListNode *tmp = head;
if (tmp == nullptr) {
return true;
}
while (tmp != nullptr) {
val_vector.push_back(tmp->val);
tmp = tmp->next;
}
int front = 0, end = val_vector.size() - 1;
while (front < end) {
if (val_vector.at(front) != val_vector.at(end)) {
return false;
}
front++;
end--;
}
return true;
}
};
|
这个效率其实更高，虽然都是O(n)；不过空间占用上还是没有什么提升……因为这次也用了一个数组，要完成题目要求的O(1)确实有些困难。
借鉴思路
其实我也有一些想法，就是把链表想办法直接反向遍历，但是没成功，要么是达不到O(1)，要么是速率跟不上了。原因是没找到好的反转链表的思路，这里借鉴大神思路：
- 找到链表的中间节点，这里使用快慢指针方法
- 将从中间节点到尾节点的这一部分倒过来
- 分别遍历原链表和新链表，如果有完全相同就是回文
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
ListNode* middleNode(ListNode* head) {
ListNode* slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr, *cur = head;
while (cur) {
ListNode* nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
public:
bool isPalindrome(ListNode* head) {
ListNode* mid = middleNode(head);
ListNode* head2 = reverseList(mid);
while (head2) {
if (head->val != head2->val) {
return false;
}
head = head->next;
head2 = head2->next;
}
return true;
}
};
|
结果如下，空间虽然只小了10MB左右，但是确实是O(1)的，整体思路还是很好的。
个人总结
想做对，在效率上达标是很简单的，关键是内存占用，也就是空间复杂度上，这个真得有一个比较好的思路去兼顾效率和空间……还是太菜了hhhh
