# 160.相交链表

<https://leetcode-cn.com/problems/intersection-of-two-linked-lists>

* [160.相交链表](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDok_dM9v36FSB_Ul#160相交链表)
  * [题目描述](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDok_dM9v36FSB_Ul#题目描述)
  * [方法 1：暴力法](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDok_dM9v36FSB_Ul#方法-1暴力法)
    * [思路](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDok_dM9v36FSB_Ul#思路)
    * [复杂度](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDok_dM9v36FSB_Ul#复杂度)
    * [代码(JavaScript/C++)](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDok_dM9v36FSB_Ul#代码javascriptc)
  * [方法 2：哈希表](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDok_dM9v36FSB_Ul#方法-2哈希表)
    * [思路](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDok_dM9v36FSB_Ul#思路-1)
    * [复杂度](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDok_dM9v36FSB_Ul#复杂度-1)
    * [代码(JavaScript/C++)](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDok_dM9v36FSB_Ul#代码javascriptc-1)
  * [方法 3：双指针](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDok_dM9v36FSB_Ul#方法-3双指针)
    * [思路](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDok_dM9v36FSB_Ul#思路-2)
    * [复杂度](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDok_dM9v36FSB_Ul#复杂度-2)
    * [代码(JavaScript/C++)](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDok_dM9v36FSB_Ul#代码javascriptc-2)

## 题目描述

```
编写一个程序，找到两个单链表相交的起始节点。

https://leetcode-cn.com/problems/intersection-of-two-linked-lists
```

## 方法 1：暴力法

### 思路

对于链表 A 的每个节点，都去链表 B 中遍历一遍找看看有没有相同的节点。

### 复杂度

* 时间复杂度：$O(M \* N)$, M, N 分别为两个链表的长度。
* 空间复杂度：$O(1)$。

### 代码(JavaScript/C++)

JavaScript Code

```javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
    if (!headA || !headB) return null;

    let pA = headA;
    while (pA) {
        let pB = headB;

        while (pB) {
            if (pA === pB) return pA;
            pB = pB.next;
        }

        pA = pA.next;
    }
};
```

C++ Code

```cpp
/**
 * 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) {
        if (headA == NULL || headB == NULL) return NULL;

        ListNode *pA = headA;

        while (pA != NULL) {
            ListNode *pB = headB;
            while (pB != NULL) {
                if (pA == pB) {
                    return pA;
                }
                pB = pB->next;
            }
            pA = pA->next;
        }
        return NULL;
    }
};
```

## 方法 2：哈希表

### 思路

* 先遍历一遍链表 A，用哈希表把每个节点都记录下来(注意要存节点引用而不是节点值)。
* 再去遍历链表 B，找到在哈希表中出现过的节点即为两个链表的交点。

### 复杂度

* 时间复杂度：$O(M + N)$, M, N 分别为两个链表的长度。
* 空间复杂度：$O(N)$，N 为链表 A 的长度。

### 代码(JavaScript/C++)

JavaScript Code

```javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
    if (!headA || !headB) return null;

    const hashmap = new Map();

    let pA = headA;
    while (pA) {
        hashmap.set(pA, 1);
        pA = pA.next;
    }

    let pB = headB;
    while (pB) {
        if (hashmap.has(pB)) return pB;
        pB = pB.next;
    }
};
```

C++ Code

```cpp
/**
 * 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) {
        if (headA == NULL || headB == NULL) return NULL;

        map<ListNode*, bool> seen;
        while (headA) {
            seen.insert(pair<ListNode*, bool>(headA, true));
            headA = headA->next;
        }
        while (headB) {
            if (seen.find(headB) != seen.end()) return headB;
            headB = headB->next;
        }
        return NULL;
    }
};
```

## 方法 3：双指针

### 思路

![](https://cdn.jsdelivr.net/gh/suukii/91-days-algorithm/assets/intersection_of_linked_lists.png)

**如果链表有交点**

![](https://cdn.jsdelivr.net/gh/suukii/91-days-algorithm/assets/intersection_of_linked_lists_1.png)

**如果链表没有交点**

1. 两个链表长度一样，第一次遍历结束后 pA 和 pB 都是 null，结束遍历
2. 两个链表长度不一样，两次遍历结束后 pA 和 pB 都是 null，结束遍历

### 复杂度

* 时间复杂度：$O(M + N)$, M, N 分别为两个链表的长度。
* 空间复杂度：$O(1)$。

### 代码(JavaScript/C++)

```javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
    if (!headA || !headB) return null;

    let pA = headA,
        pB = headB;
    while (pA !== pB) {
        pA = pA === null ? headB : pA.next;
        pB = pB === null ? headA : pB.next;
    }
    return pA;
};
```

C++ Code

```cpp
/**
 * 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) {
        if (headA == NULL || headB == NULL) return NULL;

        ListNode* pA = headA;
        ListNode* pB = headB;
        while (pA != pB) {
            pA = pA == NULL ? headB : pA->next;
            pB = pB == NULL ? headA : pB->next;
        }

        return pA;
    }
};
```

更多题解可以访问：<https://github.com/suukii/91-days-algorithm>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://suki.gitbook.io/91-days-algorithm/basic/linked-list/10.intersection-of-two-linked-lists.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.