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

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        // 思路：求两个链表长度，让长的先走一段距离，再一起出发，遇到一样的就是第一个节点
        // 这种方法是理解起来最简单的，但是需要计算链表的长度
        // 另外一种方法，就是，把两个链表合起来看，链表1和链表2同时出发，链表1如果走完了，从链表2出发，链表2走完了，从链表1出发
        // 一样的路程，一样的速度，他们总会相遇的，第一次相遇地方就是公共节点
        
        ListNode l1 = pHead1, l2 = pHead2;
        while(l1 != l2){
            l1 = l1 == null ? pHead2 : l1.next;
            l2 = l2== null ? pHead1 : l2.next;
        }
        return l1;

 
    }
}

在思路里面我说了，最好理解方法就是，先求出长度差，然后长的先走差值长度，再比较是否相同。这种方法还需要计算链表的长度。

另外一种方法，是合并两个链表，他们的路程一样，速度一样，总会相遇的。这种情况要注意，我一开始是判断，l1.next == null ，这会出现一个问题，就是当两个链表没有重叠的时候，会陷入死循环。并且一开始还需要增加一个判断，就是一开始如果链表为空，就要输出null。

所以更改了思路，增加链表尾null，路程还是一样的，判断的是l1 == null ,如果两个链表都走到了彼此结束的地方，都为null，此时l1是等于l2的，会跳出循环，并且一开始的判断链表是否为空也不需要了。