# 160.相交链表

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

* [160.相交链表](#160相交链表)
  * [题目描述](#题目描述)
  * [方法 1：暴力法](#方法-1暴力法)
    * [思路](#思路)
    * [复杂度](#复杂度)
    * [代码(JavaScript/C++)](#代码javascriptc)
  * [方法 2：哈希表](#方法-2哈希表)
    * [思路](#思路-1)
    * [复杂度](#复杂度-1)
    * [代码(JavaScript/C++)](#代码javascriptc-1)
  * [方法 3：双指针](#方法-3双指针)
    * [思路](#思路-2)
    * [复杂度](#复杂度-2)
    * [代码(JavaScript/C++)](#代码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>