# \[160]\[简单]\[双指针] 相交链表

## 题目描述

[160. 相交链表](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/) [剑指 Offer 52. 两个链表的第一个公共节点](https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/)

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

如下面的两个链表：

![](/files/-MI7NrnjUIpVAESBWZX8)

在节点 c1 开始相交。

示例 1：

![](/files/-MI7NrnkHUWXyIfqlo3O)

```
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
```

示例 2：

![](/files/-MI7NrnlFu7UmGS9rJ8n)

```
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
```

示例 3：

![](/files/-MI7NrnmgLndT7SoxJa9)

```
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
```

注意：

* 如果两个链表没有交点，返回 null.
* 在返回结果后，两个链表仍须保持原有的结构。
* 可假定整个链表结构中没有循环。
* 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

## 解题思路

定义两个指针分别指向两个链表的头部. 每次两个链表都向后移一步, 第一个链表达到尾部时, 对应的指针切换到另一个链表的头部, 第二个链表达到尾部时, 切换指针到第一个链表的同步, 这样指针在相遇时, 都走过了相同的步数, 覆盖了相同的路径.

如果两个链表不相交, 则它们的尾节点不同, 在遍历的时候记录尾指针, 然后比较是否相同就可以剔除这种情况.

[Intersection of Two Linked Lists （双指针，链表拼接）](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/intersection-of-two-linked-lists-shuang-zhi-zhen-l/)

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a, b = headA, headB
        if not a or not b:
            return None

        tail_a, tail_b = None, None
        while a != b:
            if a.next is None:
                tail_a = a
                a = headB
            else:
                a = a.next
            if b.next is None:
                tail_b = b
                b = headA
            else:
                b = b.next
            if tail_a and tail_b and tail_a is not tail_b:
                return None
        return a
```


---

# 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://kerasnoone.gitbook.io/garnet/suan-fa/shuang-zhi-zhen/160-xiang-jiao-lian-biao.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.