双指针
解题思路
第一步：找到链表中间节点；
第二步：反转后半段链表；
第三步：判断前半段和反转的后半段链表，值是否相等；
复杂度
-
时间复杂度：
O(n)，其中 n 是链表的长度； -
空间复杂度：
O(1)；
代码实现
var isPalindrome = function (head) {
// 1. 找到中间节点
let tail = middleNode(head).next;
// 2. 反转后半段链表
tail = reverseList(tail);
// 3. 判断前半段和反转的后半段链表，值是否相等
while (tail) {
if (tail.val !== head.val) {
return false;
}
tail = tail.next;
head = head.next;
}
return true;
};
// 反转链表
var reverseList = function (head) {
let prev = null;
let curr = head;
while (curr != null) {
let nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
// 找到中间节点
var middleNode = function (head) {
let slow = head;
let fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 61. 旋转链表
上一篇
评论
