題目描述：輸入兩個鏈表，找出它們的第一個公共節(jié)點。

解法 1: 遍歷+哈希表記錄

比較容易想到的思路：

• 開辟哈希表 map。key 是節(jié)點，value 是 boolean，代表節(jié)點是否出現(xiàn)過
• 對 list1 進(jìn)行遍歷，設(shè)置 map[節(jié)點]=true
• 對 list2 進(jìn)行遍歷，如果節(jié)點在 map 中出現(xiàn)過，那么說明這是兩個鏈表的公共節(jié)點，返回

代碼實現(xiàn)如下：

// ac地址：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
// 原文地址：https://xxoo521.com/2020-03-12-list-node/
/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    const map = new Map();
    let node = headA;
    while (node) {
        map.set(node, true);
        node = node.next;
    }

    node = headB;
    while (node) {
        if (map.has(node)) return node;
        node = node.next;
    }
    return null;
};

時間復(fù)雜度是，空間復(fù)雜度是。

解法 2: 快慢指針

題目提示了，空間復(fù)雜度可以降低到。這時候不能用哈希表，可以使用快慢指針的思路來處理。整體思路如下：

• 遍歷得到兩個鏈表的長度，以及長度差 diff
• 將慢指針 slow 指向較長鏈表，快指針 fast 指向較短鏈表
• slow 向前移動 diff 個距離
• slow 和 fast 同時向前移動，每次移動一個距離。若存在公共節(jié)點，那么它們一定會遇上。

代碼實現(xiàn)是：

// ac地址：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
// 原文地址：https://xxoo521.com/2020-03-12-list-node/

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let node = headA;
    let lengthA = 0;
    while (node) {
        ++lengthA;
        node = node.next;
    }
    if (!lengthA) return null;

    node = headB;
    let lengthB = 0;
    while (node) {
        ++lengthB;
        node = node.next;
    }
    if (!lengthB) return null;

    let diff = 0,
        slow,
        fast;
    if (lengthA > lengthB) {
        slow = headA;
        fast = headB;
        diff = lengthA - lengthB;
    } else {
        slow = headB;
        fast = headA;
        diff = lengthB - lengthA;
    }

    while (diff--) {
        slow = slow.next;
    }

    while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }

    return slow;
};

時間復(fù)雜度是，空間復(fù)雜度是。效果也蠻好的，時間擊敗 95.49%，內(nèi)存擊敗 100%。截圖如下：

image

更多資料

整理不易，若對您有幫助，請給個「關(guān)注+點贊」，您的支持是我更新的動力 ??

• ??Blog：劍指 Offer 題解 + JS 代碼
• ??Github ：https://github.com/dongyuanxin/blog
• ?? 公眾號：心譚博客