[数据结构与算法]剑指 Offer II 029. 排序的循环链表（Javascript）

一、题目地址

https://leetcode-cn.com/problems/aMhZSa/

二、具体代码

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

/**
 * 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}
 */
function findFirtstHalfEnd(head) {
    let fast = head;
    let slow = head;
    while(fast.next !== null && fast.next.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}
function reverseSecondHalf(head) {
    let pre = null;
    let cur = head;
    while(cur !== null) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}
var isPalindrome = function(head) {
    if(head === null) {
        return true;
    }
    let firstHalfEnd = findFirtstHalfEnd(head);
    let secondHalfStart = reverseSecondHalf(firstHalfEnd.next);
    let p1 = head;
    let p2 = secondHalfStart;
    let result = true;
    while(result && p2 !== null) {
        if(p1.val !== p2.val) {
            result = false;
        }
        p1 = p1.next;
        p2 = p2.next;
    }
    //还原链表本身
    firstHalfEnd.next = reverseSecondHalf(secondHalfStart);
    return result;
};

三、补充链接

https://leetcode-cn.com/problems/aMhZSa/solution/hui-wen-lian-biao-by-leetcode-solution-3q3r/