leetcode234-回文链表

leetcode 234

思路

利用快慢指针法+链表反转实现

对于链表反转的实现，在之前的博文里面有记录：链表反转
快慢指针的核心思想是找到链表的中点，把中点后面的部分进行反转，然后把后半部分反转后的链表和前半部分进行比较，如果一致则说明是回文链表

为什么利用快慢指针可以找点链表中点呢？

因为快指针走两步，慢指针走一步，快指针走的步长是慢指针的两倍，当快指针走到末尾的时候，慢指针刚好走了一半
具体步骤如下：

• 找到链表中点：使用快慢指针，快指针 fast 每次移动两步，慢指针 slow 每次移动一步。当快指针 fast 到达链表末尾或者 fast 的下一个节点为空时，慢指针 slow 正好指向链表的中点（如果链表长度为偶数，slow 指向的是前半部分的最后一个节点）
• 反转链表后半部分：从 slow 的下一个节点开始，对链表的后半部分进行反转操作。这里可以使用经典的链表反转算法，通过改变节点的指针方向实现链表反转
• 比较前后两部分：设置两个指针，一个指针 p1 指向链表头节点 head ，另一个指针 p2 指向反转后的后半部分链表的头节点。然后依次比较 p1 和 p2 指向节点的 val 值，如果在比较过程中发现不相等的值，直接返回 false ；如果能顺利比较完所有节点，则返回 true

实现

var isPalindrome = function (head) {let slow = head, fast = head;while (fast && fast.next) {slow = slow.next;fast = fast.next.next;}// 反转后半部分链表let reverse = getReverseList(slow);while (reverse) {if (reverse.val !== head.val) {return false}reverse = reverse.next;head = head.next}return true
};// 获取反转链表
function getReverseList(head) {let pre = null;let cur = head;while (cur) {const node = cur.next;cur.next = pre;pre = cur;cur = node;}return pre;
}

实现链表

一般leetcode上的题目都是给的一个数组：head = [1,2]，我们想要去调试，需要手动将这个数组转换为链表的类型，下面就是数组转链表的实现函数

export class Nodelist {constructor(value) {this.val = value;this.next = null}
}export function getNode(arr) {const head = new Nodelist(arr[0])const len = arr.length;let cur = head;for (let i = 1; i < len; i++) {cur.next = new Nodelist(arr[i])cur = cur.next;}return head
}