相交链表

## 题目

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

如下面的两个链表：

![](https://notebook.ricear.com/media/202105/2021-05-24_203625.png)

在节点 c1 开始相交。

**示例 1：**

![](https://notebook.ricear.com/media/202105/2021-05-24_203718.png)

```txt
输入：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：**

![](https://notebook.ricear.com/media/202105/2021-05-24_203739.png)

```txt
输入：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：**

![](https://notebook.ricear.com/media/202105/2021-05-24_203755.png)

```txt
输入：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) 内存。

## 解题思路

### HashMap

#### 问题解析

1. 将一个链表中的所有节点信息存入到**HashMap**中：

* **key**：当前节点的地址
   * **Value**：当前节点的父节点（头结点的父节点为**null**）
2. 然后依次遍历另一个链表：

1. 如果**HashMap**中包含当前节点的**key**，同时其对应的**value**不等于当前节点的父节点，则当前节点即为两个链表相交的起始节点。
   2. 如果遍历到最后不存在的话，则直接返回**null**。

![](https://notebook.ricear.com/media/202105/2021-05-24_211658.png)

#### 参考代码

```java
/**
 * 160. 相交链表
 * @param headA 第一个链表的头结点
 * @param headB 第二个链表的头结点
 * @return
 */
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //  解决 headA 和 headB 相同的情况
    if (headA == headB) {return headA;}
    Map<ListNode, ListNode> map = new HashMap<>();
    ListNode p = headA, prev = null;
    while (p != null) {
        map.put(p, prev);
        prev = p;
        p = p.next;
    }
    p = headB;
    prev = null;
    while (p != null) {
        if (map.containsKey(p) && map.get(p) != prev) {return p;}
        prev = p;
        p = p.next;
    }
    return null;
}
```

### 双指针

> 两个指针最后 **一定会相等**。

#### 问题解析

1. 开始时令指针**head1=headA**，**head2=headB**。
2. 然后两个指针分别从两个链表的起点开始遍历：
   1. 当其中一个指针到达链表的尾部时，则令其等于**另一个链表**的**头部**，然后继续开始遍历，例如**head1**遍历到**headA**的尾部时，令**head1=headB**。
3. 在两次遍历的过程中，因为两个指针最终走的路程一样，所以：
   1. 如果两个链表相交时，两个指针一定会在两个链表相交的节点相遇。
   2. 如果两个链表不相交时，最后两个指针一定会在链表的尾部相遇，即两个指针最后的值都为**null**。

![](https://notebook.ricear.com/media/202105/2021-05-24_204857.png)

将二者的路径拼接到一起进行展示：

![](https://notebook.ricear.com/media/202105/160-相交链表（解法二：双指针）（展示方法二）_1621860793.gif)

#### 参考代码

```java
/**
 * 160. 相交链表
 * @param headA 第一个链表的头结点
 * @param headB 第二个链表的头结点
 * @return
 */
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //  如果 headA 或 headB 为 null，则两个链表肯定不相交，直接返回 null
    if (headA == null || headB == null) {return null;}
    ListNode head1 = headA, head2 = headB;
    //  两次遍历：
    //      如果两个链表有交点，则最后 head1 一定为二者的交点
    //      如果两个链表没有交点，则一定是在最后到尾节点的时候二者相遇，此时 head1 为 null
    while (head1 != head2) {
        if (head1 == null) {
            //  如果 head1 走到了尾节点，则令其等于 headB 的头结点
            head1 = headB;
        } else {
            //  否则的话，继续遍历即可
            head1 = head1.next;
        }

if (head2 == null) {
            //  如果 head2 走到了尾节点，则令其等于 headA 的头结点
            head2 = headA;
        } else {
            //  否则的话，继续遍历即可
            head2 = head2.next;
        }
    }
    return head1;
}
```

## 参考文献

1. [160. 相交链表](https://leetcode-cn.com/problems/intersection-of-two-linked-lists)。
2. [图解相交链表](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/tu-jie-xiang-jiao-lian-biao-by-user7208t)。