题目描述

输入两个无环的单链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
示例1
输入：{1,2,3},{4,5},{6,7}
返回值：{6,7}
说明：第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分，这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的。

题目分析

题目中所讲的链表的公共结点，是指相同的结点对象，而非只是简单的值相同，若两链表有公共结点，则有如下图的链表结构：
图片说明
链表1和链表2的公共结点部分为{6,7}，第一个公共结点为6，可以通过遍历链表1和链表2，判断结点对象第一个相同的即为第一个公共结点。

解题思路

方法1：使用hashset来保存结点
1.首先遍历一遍链表1，并将所有结点都放入到hashset中
2.在遍历链表2的过程，判断hashset中是否存在此结点
3.若是存在，则第一次发现存在的，就是第一个公共结点，直接返回；若是遍历完链表2，仍不存在，则返回null

方法2：使用双指针
使用两个指针变量同时遍历两个链表，因为非公共部分的长度不一定相同，所以遍历到相同部分的时间也不一样；
图片说明
通过将链表1到达链表尾部后，继续指向链表2，而链表2则指向链表1，继续遍历，则这次遍历中两个指针cur1和cur2必定会相遇：
假设链表1非公共部分长度为A，链表2非公共部分长度为B，公共长度为C，则有：
(A+C) + B = (B+C) + A
即cur1和cur2第一次相遇的条件，当链表有公共结点时，cur1和cur2指向的是第一个公共结点；当没有公共结点时，cur和cur2都是null。

代码实现

方法1：使用hashset来保存结点

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode current1 = pHead1;
        ListNode current2 = pHead2;
        // 借助hashset
        HashSet<ListNode> set = new HashSet<ListNode>();
        while (current1 != null) {
            // 遍历一遍链表1，将链表1中的结点都加入到set中
            set.add(current1);
            current1 = current1.next;
        }
        while (current2 != null) {
            // 在遍历链表2的时候，若set中包含该结点，则此结点为第一个公共结点
            if (set.contains(current2))
                return current2;
            current2 = current2.next;
        }
        // 若都遍历完，则没有公共结点
        return null;
    }

时间复杂度：O(n+m)，n和m分别为链表1和链表2的长度，最差情况下没有公共结点，则需要遍历两个链表；
空间复杂度：O(n)，需要在set中存储链表1的所有结点。

方法2：使用双指针

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode current1 = pHead1;
        ListNode current2 = pHead2;
        while(current1 != current2){
            // 当链表1已经到末尾时，转到链表2遍历
            current1 = current1 == null ? pHead2 : current1.next;
            // 当链表2已经到末尾时，转到链表1遍历
            current2 = current2 == null ? pHead1 : current2.next;
        }
        // 退出循环的情况可能有两种：c1和c2均为第一个公共结点；c1和c2均为null
        return current1;
    }

时间复杂度：O(n+m)，n和m分别为链表1和链表2的长度，最差情况下没有公共结点，则需要遍历两个链表；
空间复杂度：O(1)，只需要两个变量来遍历链表1和链表2，空间复杂度为O(1)。