一、题目

给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须保持其原始结构。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/intersection-of-two-linked-lists

读者可以先暂停思考一下，看看自己自己有没有解题的思路。

二、思路

2.1 确定算法

首先，我们先选择使用什么样的算法来求解此题。

2.1.1 哈希集合

我第一眼看到这个题目的时候，想到的是使用哈希集合来辅助解决这个问题，首先遍历链表headA，并将链表headA中的每个节点加入哈希集合中。
然后遍历链表headB，对于遍历到的每个节点，判断该节点是否在哈希集合中，两种情况：
1. 如果当前节点不在哈希集合中，则继续遍历下一个节点；
2. 如果当前节点在哈希集合中，则后面的节点都在哈希集合中，则该节点就是我们要的答案，返回该节点。
如果链表headB中的所有节点都不在哈希集合中，则两个链表不相交，返回null。

上面就是使用哈希集合来进行求解的一个思路分析，并不难理解，感兴趣的同学可以自己尝试写一下对应的算法代码。

2.1.2 双指针

今天我们不谈使用哈希集合的解法，而是选择使用双指针技巧来进行求解。
有些同学可能不知道双指针是啥，或者还是第一次听到指针这个概念。
- 指针：一种用于存储和访问内存地址的数据类型，可以指向任何数据类型（如int、float、double等）的内存地址。指针变量可以用来间接访问存储在该地址上的值。指针常常被用于动态内存管理、传递参数和数据结构中，特别是链表和树等。
学过C语言的都知道，指针是个相对麻烦的东西。但是双指针中的’指针’并不一定指向某个内存地址，它可以是数组的索引、可以是字符串的某个字符的索引、可以是某个链表节点等等（虽然索引在根本上也是内存地址，这里不深究）
- 使用双指针可以很好的帮我们解决一些数组和链表方面的问题，并且使用起来也很方便，经过后面的算法分析后相信你会有一个比较深的感悟。
- 一般来说，如果问题需要定位两个指针在数组或链表上的位置，并要求这两个指针相互配合，分别从两端向中间遍历以达到某种目的，就可以考虑使用双指针算法。

举个例子可能更有利于理解，下面是一个使用双指针技巧判断字符串是否为回文字符串的算法：

class Solution {
    public boolean isPalindrome(String s) {
        StringBuffer sgood = new StringBuffer();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                sgood.append(Character.toLowerCase(ch));
            }
        }
        int n = sgood.length();
        int left = 0, right = n - 1;
        while (left < right) {
            if (Character.toLowerCase(sgood.charAt(left)) != Character.toLowerCase(sgood.charAt(right))) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
}

2.2 算法分析

可能现在你对双指针依然只有个模糊的概念，没关系，进行算法分析将有助于我们进一步理解双指针的含义。

2.2.1 定义指针

再看一下题目：给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。
我们先来定义两个指针：分别指向headA和headB。需要注意，大多数链表的题目都要求我们保持原始的链表结构！ 所以不建议直接使用链表的头结点。

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /*  省略  */
        ListNode pA = headA;
        ListNode pB = headB;
        /*  省略  */
    }
}

2.2.2 核心算法

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /*  省略  */
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        /*  省略  */
    }
}

上面的代码就是整个算法的灵魂，解释一下：
pA = pA == null ? headB : pA.next;
- 这段代码翻译一下：先判断pA是否为null，如果为null，则pA指向headB的头节点，否则，pA指向pA的下一个节点。
pB = pB == null ? headA : pB.next;
- 这段代码同理：先判断pB是否为null，如果为null，则pB指向headA的头节点，否则，pB指向pB的下一个节点。
自始至终，没有改变headA和headB中任意一个节点的指向，即保留了原始的链表结构。同时，解决了问题，直接return pA或者pB就得到了我们需要的那个相交节点（如果存在），否则会返回null（此时pA和pB也都为null）。

2.2.3 思路总结

Amazing！怎么回事呢？这个要用文字解释起来有一点点麻烦，我们直接看图（图是评论区的，我觉得画的挺好）：

做个大白话分析：
1. 首先，我们维护两个指针 pA 和 pB，分别指向链表 A 和链表 B 的头节点；
2. 然后，同时遍历链表 A 和链表 B，每次让 pA 和 pB 分别向后移动一个节点，直到其中一个链表到达链表尾部（即为 null）为止；
3. 如果两个链表不相交，则 pA 和 pB 会同时到达各自链表的尾节点，此时返回 null；
4. 如果两个链表相交，则在某个节点处 pA 和 pB 会相遇。此时，pA 移动的距离等于链表 B 头部到交点的距离加上从交点到相遇点的距离，pB 移动的距离等于链表 A 头部到交点的距离加上从交点到相遇点的距离。所以，当 pA 和
  pB 相遇时，它们所遍历的路程长度相等；
5. 最后，让 pA 和 pB 分别指向另一个链表的头节点，然后再次遍历两个链表，直到它们相遇。这样做可以使 pA 和 pB 在第二次遍历时同步，继续前进直到到达交点。具体来说，在第一次遍历时，如果 pA
  遍历完了自己的链表但还没有找到交点，则将 pA 指向另一个链表的头节点；同理，如果 pB 遍历完了自己的链表但还没有找到交点，则将 pB 指向另一个链表的头节点。然后，继续遍历两个链表，直到 pA 和 pB
  相遇为止，此时它们指向的节点就是链表的交点。
时间复杂度为 O(m+n)，空间复杂度为 O(1)。在实际工程中，双指针相遇法还可以用于解决其他的链表问题，如判断链表是否成环并找到环的起点等。

三、题解

下面就是一个完整的解题算法：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {//排除特殊情况
            return null;
        }
        ListNode pA = headA, pB = headB;//定义双指针
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;//return pB当然也一样，并且不会漏掉为null的情况
    }
}