题目
234. 回文链表
https://leetcode-cn.com/problems/palindrome-linked-list/
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
你能否用 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 arr = [];
// while(head) {
// arr.push(head.val);
// head = head.next;
// }
// let left = 0;
// let right = arr.length - 1;
// while (left <= right) {
// if(arr[left] !== arr[right]) return false;
// left++;
// right--;
// }
// return true;
// };
var isPalindrome = function(head) {
if(!head || !head.next) return true;
// 慢指针
let slow = head;
// 快指针
let fast = head;
// 快指针走完时,慢指针正好处于中间位置
while(fast && fast.next && fast.next.next){
slow = slow.next;
fast = fast.next.next;
}
// 反转链表,从慢指针开始的位置
let revSlow = reverseList(slow);
// 比较两个链表
while(revSlow && head){
if(revSlow.val !== head.val) return false;
revSlow = revSlow.next;
head = head.next;
}
return true;
};
// 反转链表
function reverseList(head) {
// 初始化指针
let pre = null;
// 临时变量
let next = null;
while(head){
// 保存下一个节点
next = head.next;
// 当前节点指向pre
head.next = pre;
// 修改pre
pre = head;
// 执行下一个节点
head = next;
}
return pre;
};
官方
快慢指针
思路
避免使用 O(n)额外空间的方法就是改变输入。
我们可以将链表的后半部分反转(修改链表结构),然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例,但是使用该函数的人通常不希望链表结构被更改。
该方法虽然可以将空间复杂度降到 O(1),但是在并发环境下,该方法也有缺点。在并发环境下,函数运行时需要锁定其他线程或进程对链表的访问,因为在函数执行过程中链表会被修改。
算法
整个流程可以分为以下五个步骤:
- 找到前半部分链表的尾节点。
- 反转后半部分链表。
- 判断是否回文。
- 恢复链表。
- 返回结果。
执行步骤一,我们可以计算链表节点的数量,然后遍历链表找到前半部分的尾节点。
我们也可以使用快慢指针在一次遍历中找到:慢指针一次走一步,快指针一次走两步,快慢指针同时出发。当快指针移动到链表的末尾时,慢指针恰好到链表的中间。通过慢指针将链表分为两部分。
若链表有奇数个节点,则中间的节点应该看作是前半部分。
步骤二可以使用「206. 反转链表」问题中的解决方法来反转链表的后半部分。
步骤三比较两个部分的值,当后半部分到达末尾则比较完成,可以忽略计数情况中的中间节点。
步骤四与步骤二使用的函数相同,再反转一次恢复链表本身。
const reverseList = (head) => {
let prev = null;
let curr = head;
while (curr !== null) {
let nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
const endOfFirstHalf = (head) => {
let fast = head;
let slow = head;
while (fast.next !== null && fast.next.next !== null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
var isPalindrome = function(head) {
if (head == null) return true;
// 找到前半部分链表的尾节点并反转后半部分链表
const firstHalfEnd = endOfFirstHalf(head);
const secondHalfStart = reverseList(firstHalfEnd.next);
// 判断是否回文
let p1 = head;
let p2 = secondHalfStart;
let result = true;
while (result && p2 != null) {
if (p1.val != p2.val) result = false;
p1 = p1.next;
p2 = p2.next;
}
// 还原链表并返回结果
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
};