234.回文链表
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
示例 1:
输入:head = [1,2,2,1]
输出:true
示例 2:
输入:head = [1,2]
输出:false
提示:
链表中节点数目在范围[1, 105] 内 0 <= Node.val <= 9
进阶: 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
解法
解法一:将回文链表问题转成回文字符串问题
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function (head) {
const queue = [];
while (head) {
queue.push(head.val);
head = head.next;
}
return queue.join() === queue.reverse().join();
};
解法二: 国际站的 most votes
This can be solved by reversing the 2nd half and compare the two halves. Let's start with an example [1, 1, 2, 1].
In the beginning, set two pointers fast
and slow
starting at the head.
1 -> 1 -> 2 -> 1 -> null
sf
(1) Move: fast pointer goes to the end, and slow
goes to the middle.
1 -> 1 -> 2 -> 1 -> null
s f
(2) Reverse: the right half is reversed, and slow pointer becomes the 2nd head.
1 -> 1 null <- 2 <- 1
h s
(3) Compare: run the two pointers head and slow together and compare.
1 -> 1 null <- 2 <- 1
h s
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function (head) {
let fast = head,
slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
if (fast != null) {
// odd nodes: let right half smaller
slow = slow.next;
}
slow = reverse(slow);
fast = head;
while (slow != null) {
if (fast.val != slow.val) {
return false;
}
fast = fast.next;
slow = slow.next;
}
return true;
};
function reverse(head) {
let prev = null;
while (head != null) {
let next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
来,看看结果!