---
tags: leetcode
---

# [160. Intersection of Two Linked Lists](https://leetcode.com/problems/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
<!--
# Test Cases

8
[4,1,8,4,5]
[5,6,1,8,4,5]
2
3

2
[1,9,1,2,4]
[3,2,4]
3
1

0
[2,6,4]
[1,5]
3
2

0
[1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33]
[2,4,6]
17
3

1
[1]
[1]
0
0

3
[3]
[2,3]
0
1

1
[1,2,3,4,5,6,7,8,9,10,11,12,13]
[1,2,3,4,5,6,7,8,9,10,11,12,13]
0
0

-->