判断链表是否是回文链表

Example 1:

1
2
Input: 1 → 2
Output: false

Example 2:

1
2
Input: 1 → 2 → 2 → 1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?
(Try to solve this problem in O(N) time and O(1) space. Hint: Reverse part of the linked list.)


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
38
39
40
const isPalindrome = function(head) {
if(!head || !head.next){
return true;
}
if(!head.next.next){
return head.val === head.next.val;
}
let slow = head;
let fast = head;
while(fast.next && fast.next.next){
slow = slow.next;
fast = fast.next.next;
}
slow.next = reverseList(slow.next);
fast = head;
slow = slow.next;

while(slow !== null){
if(fast.val !== slow.val){
return false;
}
else{
fast = fast.next;
slow = slow.next;
}
}
return true;
};

const reverseList = function(head) {
let prev = null;
let save = null;
while(head){
save = head.next;
head.next = prev;
prev = head;
head = save;
}
return prev;
};

2.使用堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const isPalindrome = function(head) {
if(head === null) {
return true;
}

const stack = [];
let temp = head;

while(head != null) {
stack.push(head.val);
head = head.next;
}

while(temp != null) {
if (temp.val != stack.pop()) {
return false;
}
temp = temp.next;
}
return true;
};

3.使用递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const isPalindrome = function(head) {
return recurse(head);

function recurse(node){
if (node === null){
return true;
}

const isPal = recurse(node.next);

if(node.val === head.val){
head = head.next;
return isPal;
}
else{
return false;
}
}
};

4.让链表变成双向的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const isPalindrome = function(head) {
if(!head){
return true;
}

let index = head;
index.prev = null;

while(index.next){
index.next.prev = inedx;
index = index.next;
}

while(index !== head){
if(index.val === head.val){
index = index.prev;
head = head.next
}
else{
return false;
}
}
return true;
};