题解 | #两个链表的第一个公共结点#

相交情况：两条链长度分别是x+z和y+z，那么两个点把两条链都走完，需要走的长度分别是 x+z+y+z和y+z+x+z，速度相等的情况下，当点a走完x+z+y，点b同时走完y+z+x，此时一定在最后一个z的起始点相遇。

不相交情况：两条链长分别是x和y，走完两条链需要走的长度分别是x+y和y+x，速度相等情况下，点a走完x+y，点b同时走完y+x，两点在末尾相遇。两个尾节点的next都为null，跳出循环，并且返回null。

这个问题条件如果是长度相同的链表找公共结点就很简单；那么怎么把长度不同的问题转化为长度相同的问题呢，其实是用到了很朴素的思想，即a虽然不等于b，但是a+b=b+a，也就是遍历完a再接着遍历b和遍历完b再接着遍历a，他们遍历的长度是一样的，这样就转化为长度相同的问题了。原创者确实厉害。

public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode p1=pHead1;
        ListNode p2=pHead2;
        while(p1!=p2){
            p1=(p1==null?pHead2:p1.next);
            p2=(p2==null?pHead1:p2.next);
        }
        return p1;
    }
}