# 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)$


---

# 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://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/160.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.