数据结构与算法之链表: LeetCode 234. 回文链表 (Ts版)

回文链表

• https://leetcode.cn/problems/palindrome-linked-list/description/

描述

• 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表
• 如果是，返回 true ；否则，返回 false

示例 1

输入：head = [1,2,2,1]
输出：true

示例 2

输入：head = [1,2]
输出：false

提示

• 链表中节点数目在范围[1, $10^5$] 内
• 0 <= Node.val <= 9
• 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

Typescript 版算法实现

1 ) 方案1: 将值复制到数组中后用双指针法

/**
 * 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 {
    const vals = [];
    while (head) {
        vals.push(head.val);
        head = head.next;
    }
    for (let i = 0, j = vals.length - 1; i < j; ++i, --j) {
        if (vals[i] !== vals[j]) {
            return false;
        }
    }
    return true;
};

2 ) 方案2: 递归

/**
 * 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)
 *     }
 * }
 */

let frontPointer;

const recursivelyCheck = (currentNode: ListNode | null): boolean => {
    if (currentNode) {
        if (!recursivelyCheck(currentNode.next)) {
            return false;
        }
        if (currentNode.val !== frontPointer.val) {
            return false;
        }
        frontPointer = frontPointer.next;
    }
    return true;
}
function isPalindrome(head: ListNode | null): boolean {
    frontPointer = head;
    return recursivelyCheck(head);
};

3 ) 方案3: 快慢指针

/**
 * 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)
 *     }
 * }
 */

const reverseList = (head: ListNode | null): ListNode | null => {
    let prev = null;
    let curr = head;
    while (curr) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

const endOfFirstHalf = (head:ListNode | null): ListNode | null => {
    let fast = head;
    let slow = head;
    while (fast.next && fast.next.next) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

var isPalindrome = function(head:ListNode | null):boolean {
    if (!head) return true;

    // 找到前半部分链表的尾节点并反转后半部分链表
    const firstHalfEnd = endOfFirstHalf(head);
    const secondHalfStart = reverseList(firstHalfEnd.next);

    // 判断是否回文
    let p1 = head;
    let p2 = secondHalfStart;
    let result = true;
    while (result && p2) {
        if (p1.val != p2.val) result = false;
        p1 = p1.next;
        p2 = p2.next;
    }        

    // 还原链表并返回结果
    firstHalfEnd.next = reverseList(secondHalfStart);
    return result;
};