234 Palindrome Linked List
判断链表是否是回文链表, 可以的话, O(n)时间复杂度, O(1)空间复杂度.
Determine whether the given single-linked list is a palindrome linked list.
Flow up: O(n) time and O(1) space.
my solution
单链表, 时间O(n), 空间O(1), 同时满足有点难啊 = = …
It’s a little difficult to solve this question with both O(n) time and O(1) space.
我能相出的办法仅在知道链表长度/链表尾节点的情况下适用.
I can solve this if I know the length of the linked list
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
38
39
40
41
42
43
44
45
46
47
48
| class Solution {
public:
bool isPalindrome(ListNode* head) {
int n = 0;
ListNode* cursor = head;
if (cursor) {
++n;
cursor = cursor->next;
}
if (n == 1) return true;
ListNode *prev = head;
LisTNode *next = prev->next;
for (int i = 1; i < n / 2; ++i) {
ListNode *tmp = next->next;
next->next = prev;
prev = next;
next = tmp;
}
if (n & 1)
next = next->next;
while (next) {
if (next->val != prev->val)
return false;
next = next->next;
prev = prev->next;
}
return true;
}
};
|
知道了节点长度的话, 不断反向节点, 直到到达中间节点, 然后从中间节点向两端对比就好了, 两次循环各遍历一半的节点. 所以还算 O(1), 空间只需要必须的用于遍历的节点, O(1)也满足. 但问题就是这是节点长度的情况下. 所以很好奇什么算法可以满足这两个需求. (其实看了之后感觉 = = , emmm… 没有很惊艳)
If know the length of the linked list, reverse nodes until the center of the linked list, then compare elements between the center node.
best solution
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
| class Solution {
public:
bool isPalindrome(ListNode* head) {
if (!head || !head->next) return true;
ListNode* slow = head;
ListNode* fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
slow->next = reverseList(slow->next);
slow = slow->next;
while (slow) {
if (head->val != slow->val) return false;
head = head->next;
slow = slow->next;
}
return true;
}
ListNode* reverseList(ListNode* head) {
if (head == NULL) {
return head;
}
ListNode* currentHead = head;
while (head->next) {
ListNode* p = head->next;
head->next = p->next;
p->next = currentHead;
currentHead = p;
}
return currentHead;
}
};
|
办法几乎和我相同, 核心就是那个中间节点, 结果是用这种方法来解决的… 怎么没想到呢 = =, 学到了学到了…
还有就是, 我在奇偶长度上花了些心思, 所以从 1 开始循环, 并且对两种情况做了处理.
但是这种方法的话, 因为并不是由内向外, 所以奇偶不重要, 也不需要额外的代码来处理了.