234. Palindrome Linked List

BF

实现

遍历链表，存进数组，然后首尾两两比较。

提示I - Reverse

实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
const isPalindrome = (head) => {
    if (head === null || head.next === null) return true;

    const reversedList = cloneAndReverse(head);
    return checkEqual(head, reversedList);
};

const cloneAndReverse = (head) => {
    let lastNode = null, p = head;
    
    while (p != null) {
        const newNode = new ListNode(p.val);
        newNode.next = lastNode;
        lastNode = newNode;
        p = p.next;
    }

    return lastNode;
};

const checkEqual = (list, reversedList) => {
    let l1 = list, l2 = reversedList;

    while (l1 !== null && l2 !== null) {
        if (l1.val !== l2.val) return false;
        l1 = l1.next;
        l2 = l2.next;
    }

    return true;
}

提示II - Stack

实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
const isPalindrome = function (head) {
    if (head === null || head.next === null) return true;

    const { slowPointer, firstHalfStack } = generateFirstHalfStack(head);
    return checkEqual(slowPointer, firstHalfStack);
};

const generateFirstHalfStack = (head) => {
    const firstHalfStack = [];

    let slowPointer = head, fast = head;

    while (fast !== null && fast.next !== null) {
        firstHalfStack.push(slowPointer.val);
        slowPointer = slowPointer.next;
        fast = fast.next.next;
    }

    // skip the middle element when length is odd
    if (fast !== null) { 
        slowPointer = slowPointer.next;
    }

    return {
        firstHalfStack,
        slowPointer
    }
};

const checkEqual = (slowPointer, firstHalfStack) => {
    while (slowPointer !== null) {
        if (slowPointer.val !== firstHalfStack.pop()) return false;
        slowPointer = slowPointer.next;
    }

    return true;
}

提示III - Recursive

实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
const isPalindrome = function (head) {
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    const mid = slow;

    if (fast !== null) slow = slow.next;

    const f = (p) => {
        if (p === mid) {
            return true;
        }

        const t = f(p.next) && (p.val === slow.val);
        slow = slow.next;
        return t;
    }

    return f(head);
}

提示IV - One Pass

实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
const isPalindrome = function (head) {
    if (head === null || head.next === null) return true;

    let slow = head;
    let fast = head;
    let last = null;

    while (fast !== null && fast.next !== null) {
        fast = fast.next.next;

        const next = slow.next;
        slow.next = last;
        last = slow;
        slow = next;
    }

    if (fast !== null) slow = slow.next;

    while (last !== null) {
        if (last.val !== slow.val) return false;
        last = last.next;
        slow = slow.next;
    }

    return true;
}