234. 回文链表

题目链接：https://leetcode.cn/problems/palindrome-linked-list/

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function isPalindrome(head: ListNode | null): boolean {
    let arr = [];
    while (head) {
        arr.push(head.val);
        head = head.next;
    }
    const len = arr.length;
    for (let i = 0; i < Math.floor(len << 1); i++) {
        if(arr[i] !== arr[len - i - 1]){
            return false;
        }
    }
    return true;
};

思路

使用数组辅助的方法判断链表是否为回文：

遍历链表，将所有节点的值存入数组 arr 中
使用双指针从数组两端向中间遍历：
- 左指针 i 从 0 开始
- 右指针从 len - i - 1 位置开始
- 比较 arr[i] 和 arr[len - i - 1] 是否相等
如果发现不相等的元素，返回 false；遍历完成后返回 true

这个方法简单直观，通过将链表转换为数组，利用数组的随机访问特性来判断回文。

时间复杂度 $O (n)$ ，其中 $n$ 是链表的长度
空间复杂度 $O (n)$ ，需要额外的数组存储链表值

优化方案

如果要求空间复杂度 $O (1)$ ，可以使用快慢指针找到链表中点，反转后半部分链表，然后比较前后两部分。

234. 回文链表 ​

代码 ​

思路 ​

234. 回文链表

代码

思路