LeetCode
思路
转数组双指针
typescript
/**
* 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) {
// 1. 链表转数组
const arr = []
while (head != null) {
arr.push(head.val)
head = head.next
}
// 2. 双指针
let l = 0 // 左边
let r = arr.length - 1 // 最后
for (let i = 0; i < arr.length; i++) {
if (arr[l] !== arr[r]) {
return false
}
// 两个指针向中间收拢
l++
r--
}
return true
}
快慢双指针 best!
typescript
// 反转链表
const reverseList = (head) => {
let pre = null
let cur = head
while (cur !== null) {
// 1. 用tmp存cur.next
let nextTmp = cur.next
// 2. 反转
cur.next = pre
// 3. 指针右移动
pre = cur
cur = nextTmp
}
return pre
}
// 快慢双指针找中间节点(快指针走到末尾时,慢指针在中间)
const findMiddle = (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) {
// 1. 根据中间节点,找到后半链表的开始节点
let right = findMiddle(head).next
// 2. 反转后半段链表
right = reverseList(right)
// 3. 比较前半段和后半段链表, 看他们的值是否相等
// 又是双指针 head继续用
while (right) {
if (right.val !== head.val) {
return false
}
right = right.next
head = head.next
}
return true
}