第42天。
今天的题目是Palindrome Linked List:
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
如果不考虑O(1)的空间复杂度的话，可以直接用一个栈保存，然后在对比，不过我没有实现这个方法。我的解法是先用快慢指针求链表中点，然后在翻转后面的链表（只需要O(n)的时间复杂度和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
| bool isPalindrome(ListNode* head) {
if (!head || !head->next) return true;
ListNode *fast = head;
ListNode *slow = head;
ListNode *pre = slow;
while(fast && fast->next) {
fast = fast->next->next;
pre = slow;
slow = slow->next;
}
fast = pre->next;
pre->next = nullptr;
fast = revertList(fast);
while(fast && head) {
if (fast->val != head->val)
return false;
fast = fast->next;
head = head->next;
}
return true;
}
ListNode *revertList(ListNode *head) {
if(!head || !head->next) return head;
ListNode *pre = head;
ListNode *cur = head;
while(cur) {
ListNode *t = cur->next;
cur->next = pre;
pre = cur;
cur = t;
}
head = head->next;
return pre;
}
|
然后是在dicuss中看到的解法，相当有趣的技巧：
1
2
3
4
5
6
7
8
9
10
11
12
| ListNode* temp;
bool isPalindrome(ListNode* head) {
temp = head;
return check(head);
}
bool check(ListNode* p) {
if (NULL == p) return true;
bool isPal = check(p->next) & (temp->val == p->val);
temp = temp->next;
return isPal;
}
|
刚开始看的时候感觉好像是错的，但是仔细想想，这个方法相当美妙，利用函数调用来做栈，首先是递归调用check(p->next),这样的话会一直到最后一个节点才开始比较temp->val == p->val，又因为temp = temp->next始终没有执行到，所以现在temp指向第一个元素，而p指向最后一个元素，判断完后，会执行到temp = temp->next，然后check会返回，返回后p就指向了倒数第二个元素，就这样一直迭代下去。
不过这个方法的空间复杂度是O(n).