leetcode 234. 回文链表 js 实现

/**
 * 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}
 */
//  方法一：快慢指针+反转链表法
// 1. 找到后半部分链表的头结点，即先找到前半部分的尾结点，如果链表节点数为奇数，则中间的节点算做前半段
// 2. 反转后半段链表
// 3. while 循环，遍历，遍历条件为短的链表先遍历结束
// 4. 前后两段链表值对比，当不相等则返回 false，否则返回 true
// 5. 将链表恢复原样，避免其他地方使用
// 复杂度分析
// 时间复杂度：O(n)，其中 n 指的是链表的大小。
// 空间复杂度：O(1)，我们只会修改原本链表中节点的指向，而在堆栈上的堆栈帧不超过 O(1)O(1)。
var isPalindrome = function(head) {
    if(head === null){
        return true;
    }
    // 获取前半部分链表的尾结点
    let fistHalfEnd = getFistHalfOfLinked(head);
    // 反转后半部分链表
    let secondLinked = reverseList(fistHalfEnd.next);
    // 复制头结点，以便接下来遍历
    let p1 = head;
    // 复制后半部分链表，用来遍历
    let p2 = secondLinked;
    // 定义默认返回的结果
    let result = true;
    // 当后半部分链表还存在时，进行遍历
    while(p2){
        if(p1.val !== p2.val){
            result = false;
            break;
        }
        p1 = p1.next;
        p2 = p2.next;
    }
    // 恢复链表，再次反转后半段
    fistHalfEnd.next = reverseList(secondLinked)
    return result;
};
// 反转链表
function reverseList(head){
    if(!head || !head.next){
        return head
    }
    // 定义当前节点 等于 head
    let cur = head;
    // 定义上一个节点 等于 null
    let prev = null;
    // 如果当前节点存在，在进行链表遍历
    while(cur){
        // 存储当前节点的下一个，因为一会要存为上一个
        let temp = cur.next;
        // 改变当前节点的下一个节点的指向为上一个
        cur.next = prev;
        // 向前推进一步，上一个节点变为当前节点
        prev = cur;
        // 当前节点变为原来当前节点的下一个节点
        cur = temp;
    }
    // 返回反转后的头节点
    return prev;
}

// 链表分两半，返回前半部分的链表的尾结点
// 使用快慢指针
function getFistHalfOfLinked(head){
    let fast = slow = head;
    while(fast.next && fast.next.next){
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

// 方法二：数组法
// 复杂度分析
// 时间复杂度：O(n)，其中 n 指的是链表的元素个数。
// 第一步：遍历链表并将值复制到数组中，O(n)。
// 第二步：双指针判断是否为回文，执行了 O(n/2) 次的判断，即 O(n)。
// 总的时间复杂度：O(2n) = O(n)。
// 空间复杂度：O(n)，其中 n 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。
var isPalindrome = function(head) {
    if(!head || !head.next){
        return true
    }
    let arr = [];
    while(head){
        arr.push(head.val)
        head = head.next;
    }
    let len = arr.length;
    for(let i=0,j=len-1;i<len,j>0;i++,j--){
        if(arr[i] !== arr[j]){
            return false;
        }
    }
    return true;
}