透过一道链表算法题来讲引用类型的引用地址

[aermin]

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

//找到前半部分链表的尾节点
function getEndOfFirstHalf(head) {
    let fastNode = head, slowNode = head;
    while(fastNode.next !== null && fastNode.next.next !== null) {
        fastNode = fastNode.next.next;
        slowNode = slowNode.next;
    }
    return slowNode;
}

// 反转链表
function reverseList(head) {
    let pre = null, temp, current = head;
    while(current !== null) {
        temp = current.next;
        current.next = pre;
        pre = current;
        current = temp;
    }
    return pre;
}

var isPalindrome = function(head) {
    if (head === null) return true;
    console.log('head1~', JSON.stringify(head))
    // 1.找到前半部分链表的尾节点。
    let endOfFirstHalf = getEndOfFirstHalf(head);
    console.log('head2~', JSON.stringify(head))
    // 2.反转后半部分链表。
    const reversedSecondHalf = reverseList(endOfFirstHalf.next);
    // 3.判断是否为回文。
    console.log('head3~', JSON.stringify(head))
    let equal = true, p1 = head, p2 = reversedSecondHalf;
    while(equal && p2 !== null) {
        if(p1.val !== p2.val) {
            equal = false;
        } else {
            p1 = p1.next;
            p2 = p2.next;
        }
    }
    // 4.恢复链表。
    const secondHalf = reverseList(reversedSecondHalf);
    endOfFirstHalf.next = secondHalf;
    console.log('head4~', JSON.stringify(head))
    // 5.返回结果。
    return equal;
};

log出来的head1, head3不变，是因为比如function getEndOfFirstHalf中，将head赋值给slowNode，slowNode = slowNode.next;的操作也只是直接将slowNode覆盖成新的引用地址。而log出来的head3变了，是因为slowNode和head是同一引用地址，而slowNode.xx = xxx 的改动自然也是head的改动。

slowNode = slowNode.next;，function getEndOfFirstHalf最后return的slowNode的引用地址也指向head的一部分，改动此时的slowNode, head相同引用地址的部分也会被改动到。

比如reverseList(endOfFirstHalf.next)，endOfFirstHalf 其实是上文最后return的slowNode(-1 -> -1 -> 4 -> 1 -> null)，所以slowNode.next(-1 -> 4 -> 1 -> null)这个链表，在reverseList function中的current = head;(head为-1 -> 4 -> 1 -> null), current.next = pre;(pre 为null)的这两句执行完原先传进reverseList的endOfFirstHalf.next 就等于-1 -> null了，那head就跟着变成1 - > 4 -> -1 -> -1 -> null。

有点绕，可以结合并细品这张图

回归到这道算法题本身，这个方法可以让空间复杂度只为O(1), 但缺点是，在并发环境下，函数运行时需要锁定其他线程或进程对链表的访问，因为在函数执执行过程中链表暂时断开。