> For the complete documentation index, see [llms.txt](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/160.intersection-of-two-linked-lists.md).

# 0160. 相交链表

### 题目地址(160. 相交链表)

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

### 题目描述

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

### 前置知识

* 链表
* 双指针

### 解法一: 哈希法

有 A, B 这两条链表, 先遍历其中一个，比如 A 链表, 并将 A 中的所有节点存入哈希表。

遍历 B 链表,检查节点是否在哈希表中, 第一个存在的就是相交节点

* 伪代码

```jsx
data = new Set() // 存放A链表的所有节点的地址

while A不为空{
  哈希表中添加A链表当前节点
  A指针向后移动
}

while B不为空{
  if 如果哈希表中含有B链表当前节点
    return B
  B指针向后移动
}

return null // 两条链表没有相交点
```

* 代码支持: JS

JS Code:

```js
let data = new Set();
while (A !== null) {
  data.add(A);
  A = A.next;
}
while (B !== null) {
  if (data.has(B)) return B;
  B = B.next;
}
return null;
```

**复杂度分析**

* 时间复杂度：$O(N)$
* 空间复杂度：$O(N)$

### 解法二：双指针

* 例如使用 a, b 两个指针分别指向 A, B 这两条链表, 两个指针相同的速度向后移动,
* 当 a 到达链表的尾部时,重定位到链表 B 的头结点
* 当 b 到达链表的尾部时,重定位到链表 A 的头结点。
* a, b 指针相遇的点为相交的起始节点，否则没有相交点

![](https://p.ipic.vip/m02u9c.jpg) （图 5）

为什么 a, b 指针相遇的点一定是相交的起始节点? 我们证明一下：

1. 将两条链表按相交的起始节点继续截断，链表 1 为: A + C，链表 2 为: B + C
2. 当 a 指针将链表 1 遍历完后,重定位到链表 B 的头结点,然后继续遍历直至相交点(a 指针遍历的距离为 A + C + B)
3. 同理 b 指针遍历的距离为 B + C + A

* 伪代码

```js
a = headA
b = headB
while a,b指针不相等时 {
    if a指针为空时
      a指针重定位到链表 B的头结点
    else
      a指针向后移动一位
    if b指针为空时
      b指针重定位到链表 A的头结点
    else
      b指针向后移动一位
}
return a
```

* 代码支持: JS, Python, Go, PHP

JS Code:

```js
var getIntersectionNode = function (headA, headB) {
  let a = headA,
    b = headB;
  while (a != b) {
    a = a === null ? headB : a.next;
    b = b === null ? headA : b.next;
  }
  return a;
};
```

Python Code：

```py
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a, b = headA, headB
        while a != b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a
```

Go Code:

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	// a=A(a单独部分)+C(a相交部分); b=B(b单独部分)+C(b相交部分)
	// a+b=b+a=A+C+B+C=B+C+A+C
	a := headA
	b := headB
	for a != b {
		if a == nil {
			a = headB
		} else {
			a = a.Next
		}
		if b == nil {
			b = headA
		} else {
			b = b.Next
		}
	}
	return a
}
```

PHP Code:

```php
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution
{
    /**
     * @param ListNode $headA
     * @param ListNode $headB
     * @return ListNode
     */
    function getIntersectionNode($headA, $headB)
    {
        $a = $headA;
        $b = $headB;
        while ($a !== $b) { // 注意, 这里要用 !==
            $a = $a ? $a->next : $headB;
            $b = $b ? $b->next : $headA;
        }
        return $a;
    }
}
```

**复杂度分析**

* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$