描述

输入两个无环的单链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

示例1

输入：
{1,2,3},{4,5},{6,7}

返回值：
{6,7}

说明：
第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的     

示例2

输入：
{1},{2,3},{}

返回值：
{}

说明：
2个链表没有公共节点 ,返回null，后台打印{}  

思路一

比如以上图为例，首先如果两个链表相交，那么第一个交点后面的链表都是一样的。咱们用两个指针，p1 指向 A 的头节点 a1； p2 指向 B 的头节点 b1。 当p1 和 p2 第一次相等时，这个位置就是两个链表第一个交点。
从图中可以看出， c1 是这两个链表的第一个 交点， 可是 a1 到 c1 与 b1 到 c1 的距离不等，两个指针从头节点出发，一起走，是没法第一时间同时到达第一个 交点。既然，第一趟没法同时到达，那么再往后走几趟那？
假设链表 A 总长度 m， a1 到 c1 长度为 ac，c1 到 c2 的长度为 c；链表 B 总长度 n，b1 到 c1 长度为 bc。然后，大家看看 m + bc = n + ac 这个等式。等式两边的长度是一样的，并且这样可以使 两个指针同时到达第一个交点也就是 c1.

AC 代码

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        // 当有任意一个链表为空时，两个链表都不可能有交点
         if (pHead1 == null || pHead2 == null) {
             return null;
         }
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        // 当没有相交时
        while (p1 != p2) {
            // p1 一直往前走，当走到尾部时，继续走 pHead2 链表
            p1 = p1 != null ? p1.next : pHead2;
            // 同上
            p2 = p2 != null ? p2.next : pHead1;
        }
        // 相交时 返回
        return p1;
    }

时间复杂度：O(m+n),m、n为两个链表的长度
空间复杂度：O(1)，没有使用额外的空间

思路二

还是以这个图为例子，当两个链表长度一致时这题只要两个指针同时往后走，直到相遇就能找到相遇的节点，当两个链表长度不一致的时候，咱们可以这样搞。

• 判断那个链表长度长，并计算长多少
• 然后长度长的链表的指针先走 两个链表长度的差值。
• 这时两个链表的指针，具体第一个相遇节点的距离就相等了
• 然后两个链表在一起走就可以

AC 代码

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        // 当有任意一个链表为空时，两个链表都不可能有交点
         if (pHead1 == null || pHead2 == null) {
             return null;
         }
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        int length1 = 0;
        int length2 = 0;
        // 计算两个链表的长度
        while (pHead1 != null || pHead2 != null) {
            if (pHead1 != null) {
                length1 ++;
                pHead1 = pHead1.next;
            }
            if (pHead2 != null) {
                length2 ++;
                pHead2 = pHead2.next;
            }
        }
        // pNode1 是链表长度长，先走的节点
        ListNode pNode1 = p1;
        // pNode2 是不用动的节点
        ListNode pNode2 = p2;
        // 要先走的长度
        int length = 0;
        if (length2 > length1) {
            length = length2 - length1;
            pNode1 = p2;
            pNode2 = p1;
        } else if (length1 > length2) {
            length = length1 - length2;
            pNode1 = p1;
            pNode2 = p2;
        }
        // 链表长度长的节点开始往前走
        while (length > 0) {
            pNode1 = pNode1.next;
            length --;
        }
        // 然后两个节点一起往后走，直到相遇
        while (pNode1 != null && pNode2 != null && pNode1 != pNode2) {
            pNode1 = pNode1.next;
            pNode2 = pNode2.next;
        }
        // 相交时 返回
        return pNode1;
    }

时间复杂度：O(N)，N 链表长度
空间复杂度：O(1)，没有使用额外的空间

最后

大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索：【蘑菇睡不着】交个朋友～
也可以扫描下方二维码。