感觉这种好神奇,抽象的用a, b, c分别代表A特有部分、B特有部分、公共部分(先假设它们相交)。
那么由数学公式a + b + c == b + a + c,即以链表连接结点的长度来计算,如果从A链表出发,遍历A特有部分、公共部分,然后再遍历B的特有部分,一定会和从B链表出发,遍历B特有部分、公共部分,然后再遍历A特有部分相遇,而他们走过同样的长度,相遇的时候肯定是相交的起始结点。
可以模拟模拟,理论上如此,实际上也如此。

所以可以如此写代码,分别设置两个指针tempA、tempB,当它们遍历完自己的链表之后,再遍历另一个链表,它们肯定会在交点处相遇(这也暗示着循环的结束条件是两指针相同)。
万一两个链表没有相交结点怎么办?也是一样的处理,大家可以把c = 0代入然后再分析分析。

下面展示一下代码。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
        ListNode tempA = headA;
        ListNode tempB = headB;
        while(tempA != tempB){
            // 最后一定会相交,要么是tempA == tempB,要么是两者都为空
            tempA = tempA == null ? headB : tempA.next;
            tempB = tempB == null ? headA : tempB.next; 
        }
        return tempA;
    }
}

当然还有一种解决方法是利用哈希表,用set保存A链表的结点,然后再遍历B链表,如果遇到相同的第一个结点,则说明它就是两链表相交的起始结点。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        while(headA != null){
	// 把headA的所有元素都加入到set中
            set.add(headA);
            headA = headA.next;
        }
        while(headB != null){
	// 若有相同的,马上返回
            if(set.contains(headB)){
                return headB;
            }
	// 否则继续遍历
            headB = headB.next;
        }
        return null;
    }
}