✅234. 回文链表

[Ray-56]

234. 回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

[Ray-56]

转数组解

时间复杂度 O(n) 空间复杂度 O(n)

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    const arr = [];

    while (head) {
        arr.push(head.val);
        head = head.next;
    }

    for (let i = 0, j = arr.length - 1; i < j; i++, j--) {
        if (arr[i] !== arr[j]) {
            return false;
        }
    }

    return true;
};

链表反转

时间复杂度 O(n) 空间复杂度 O(1)

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    if (!head) return true;

    let first = getMiddle(head);
    let second = reverseList(first.next);

    // console.log(first);

    let p1 = head;
    let p2 = second;
    while (p2) {
        if (p1.val !== p2.val) {
            return false;
        }
        p1 = p1.next;
        p2 = p2.next;
    }
    return true;
};

function getMiddle(head) {
    let fast = head;
    let slow = head;

    while (fast.next && fast.next.next) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

function reverseList(head) {
    let cur = head;
    let pre = null;

    while (cur) {
        const next = cur.next;

        cur.next = pre;
        pre = cur;
        cur = next;
    }

    return pre;
}