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

我们注意到，题目中明确说明了两个链表都是无环的链表，这其实就是一个暗示：我们可以人为的生成一个环来解答此题。步骤如下：
	1.我们先把任意一个链表遍历到尾节点。
	2.将尾节点指向另一个链表的头节点。这样如果两条链表有公共节点，则一定会形成一个有环链表。如果没有，则还是
无环链表。
	3.至此，此问题就变成了问题BM7了，后续不再赘述。
不过需要注意的是，当我们找到第一个公共节点时，需要将尾节点和头节点的链接断开，否则提交会报错。
import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null){
            return null;
        }
        ListNode cP1 = pHead1;
        while(cP1.next != null){//遍历到尾节点
            cP1 = cP1.next;
        }
        cP1.next = pHead2;//将两者链接
        ListNode fast = pHead1;//快指针
        ListNode slow = pHead1;//慢指针

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            //相遇之后再添加一个慢指针
            if (fast == slow) {
                ListNode slow2 = pHead1;
                while (slow != slow2) {
                    slow2 = slow2.next;
                    slow = slow.next;
                }
                cP1.next = null;//断开头尾。
                return slow;
            }
        }
        //若不形成环则说明没有公共节点。
        return null;
    }
}