160. Intersection of Two Linked Lists

---

My Solution

Solution 1

The Key Idea for Solving This Coding Question

C++ Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode *> visited;
        for (ListNode *it = headA; it != nullptr; it = it->next) {
            visited.insert(it);
        }

        for (ListNode *it = headB; it != nullptr; it = it->next) {
            auto iter = visited.find(it);
            if (iter != visited.end()) {
                return it;
            }
        }

        return nullptr;
    }
};

Time Complexity

$O(n1+n2)$

$n1$ is the number of nodes in the linked list referred by headA.

$n2$ is the number of nodes in the linked list referred by headB.

Space Complexity

$O(n1)$

Solution 2

The Key Idea for Solving This Coding Question

令 itA 與 itB 分別以 headA 與 headB 為起點，遍歷兩個單向鏈結串列。
當 itA 走到 headA 所指之單向鏈結串列末端節點的下一個節點 (即 nullptr) 時，跳到 headB 繼續遍歷 headB 所指之單向鏈結串。
當 itB 走到 headB 所指之單向鏈結串列末端節點的下一個節點 (即 nullptr) 時，跳到 headA 繼續遍歷 headA 所指之單向鏈結串。
當 itA 與 itB 各自都把兩個單向鏈結串列遍歷過一遍之後，所走步數是一樣的。所以

1. 若 headA 與 headB 所指向的單向鏈結串列有交點，則 itA 與 itB 在走過相同的步數後，會停在此兩鏈結串列的交點上。
2. 若 headA 與 headB 所指向的單向鏈結串列沒有交點，則 itA 與 itB 在走過相同的步數後，會停在此兩鏈結串列末端節點的下一個節點 (即 nullptr)。

C++ Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *itA = headA, *itB = headB;

        while (itA != itB) {
            if (itA == nullptr) {
                itA = headB;
            } else {
                itA = itA->next;
            }

            if (itB == nullptr) {
                itB = headA;
            } else {
                itB = itB->next;
            }
        }

        return itA;
    }
};

Time Complexity

$O(n1+n2)$

$n1$ is the number of nodes in the linked list referred by headA.

$n2$ is the number of nodes in the linked list referred by headB.

Space Complexity

$O(1)$

Miscellaneous