題目網址：https://leetcode.cn/problems/intersection-of-two-linked-lists/

題意：給兩個 linked list 的 head headA 和 headB, 返回兩個 linked list 相交的起始點。若不存在相交, 則返回 null。

題目保證 linked list 中不存在 cycle。

注意：函數返回後, linked list 必須保持原先的結構。

進階：設計 $O(m + n)$ time 且 $O(1)$ space 的演算法。

Solution 1：

想法：利用 hash set, 先將 headA 中的每個點 insert 到 visited 中, 然後再遍歷 headB 中的每個點, 一旦發現 visited 已存在, 則返回該點。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> visited;

        ListNode *cur = headA;
        while (cur) {
            visited.emplace(cur);
            cur = cur->next;
        }

        cur = headB;
        while (cur) {
            if (visited.find(cur) != visited.end()) {
                return cur;
            }
            cur = cur->next;
        }

        return nullptr;
    }
};
  • time：$O(m + n)$ ➔ 遍歷兩個 linked list, m 為 headA 的長度, n 為 headB 的長度
  • space：$O(m)$ ➔ visited 儲存 headA 中的所有 node

Solution 2：

想法：利用 Two Pointers, 先計算兩條 linked list 的長度, 先讓長度較長者走 abs(lenA - lenB) 步, 然後再和長度較短者同時前進, 這樣兩者就能在相交起點相遇。若兩者不存在相交, 則最後兩者會同時為 null

  • 相交

  • 不相交

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        const int lenA = getLen(headA);
        const int lenB = getLen(headB);
        ListNode *longer, *shorter;

        if (lenA >= lenB) {
            longer = headA;
            shorter = headB;
        } else {
            longer = headB;
            shorter = headA;
        }

        for (int i = 0; i < abs(lenA - lenB); ++i) {
            longer = longer->next;
        }

        while (longer != shorter) {
            longer = longer->next;
            shorter = shorter->next;
        }

        return longer;
    }

private:
    int getLen(ListNode *head) {
        int len = 0;
        while (head) {
            len++;
            head = head->next;
        }
        return len;
    }
};
  • time：$O(m + n)$ ➔ 遍歷兩個 linked list, m 為 headA 的長度, n 為 headB 的長度
  • space：$O(1)$ ➔ 只需常數空間

Solution 3：

想法：Two Pointers, 令 headA 的長度為 m, headB 的長度為 n

假設兩個 linked list 相交的部分有 c 個 node, 則 headA 中不相交的部分有 m - c 個 node, headB 中不相交的部分有 n - c 個 node

若要 l1、l2 同時在相交的起始點 node 相遇, 則要做以下操作 :

  • l1 遍歷完 headA 後, 接著遍歷 headB, 當走到 node 時 ➔ l1 走了 m + (n - c) 步

  • l2 遍歷完 headB 後, 接著遍歷 headA, 當走到 node 時 ➔ l2 走了 n + (m - c) 步

  • 此時 l1、 l2 在 node 相遇, 因為 m + (n - c) = n + (m - c)

  • 若 c == 0, 也就是兩個 linked list 不相交, 則 l1、l2 將同時變為 null

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *l1 = headA, *l2 = headB;
        while (l1 != l2) {
            l1 = (l1 == nullptr) ? headB : l1->next;
            l2 = (l2 == nullptr) ? headA : l2->next;
        }
        return l1;
    }
};
  • time：$O(m + n)$ ➔ 遍歷兩個 linked list, m 為 headA 的長度, n 為 headB 的長度
  • space：$O(1)$ ➔ 只需常數空間