剑指offer：两个链表的第一个公共结点

题目

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

数据范围： n \le 1000n≤1000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。

方法一：双指针

思路：
结论：
使用两个指针遍历两个链表，当指针指到末尾时又从头开始，如果两个链表有公共点，那么两个指针一定会在第一个公共点相遇！

注意：
curr指针在循环时的，判断条件是curr1==null? 而不是 curr1.next==null? ，一旦题目是没有公共点的链表，前者可以跳出循环return curr1即null，后者会无限循环没有结果。
实现：

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
 		ListNode curr1=pHead1;
        ListNode curr2=pHead2;
        if(curr1!=null&&curr2!=null){
            //有公共节点时，两个指针一定会相遇！！！
            while(curr1!=curr2){
                //三目运算，循环到结尾时则又令为head
                curr1= curr1==null? pHead1:curr1.next; 
                curr2= curr2==null? pHead2:curr2.next;
            }   
            return curr1;
        }else{
            return null; //任一方为null都不可能有公共点，直接返回null
        }
    }
}

注意：
任一方为null都不可能有公共点，直接返回null！

方法二：从两个链表的长度入手

思路：
题目是输入三个参数，最后一个为公共部分。也就是说，只要两个链表有公共点，那么公共点以后的都是公共部分，不会产生两个链表交叉后再分开的情况。
所以，只要截去两个链表中，长度更长的链表多出来的那一部分截点，然后使用两个指针从相同的长度的起点齐头并进遍历各自链表，两个指针一定会走到第一个公共点上去！

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int num1=getNum(pHead1);
        int num2=getNum(pHead2);
        if(pHead1==null||pHead2==null){ //有一方null即不可能有公共点！
            return null;
        }
        if(num1>num2){ //如果链表1更长
            int d=num1-num2;
            for(int i=0;i<d;i++){ //弹出多出来的d个节点，找到共同长度的起点
                pHead1=pHead1.next;}
        }else{ //如果链表2更长
                int d=num2-num1;
            for(int i=0;i<d;i++){ //弹出多出来的d个节点，找到共同长度的起点
                pHead2=pHead2.next;}
            }
        
        while(pHead1!=null&&pHead2!=null){
            if(pHead1==pHead2){
                    return pHead1;} //可能第一轮就会遇到公共点，所以将判断放在移动指针前 ！
            pHead1=pHead1.next;
            pHead2=pHead2.next;
        }
        return null;
    }
    
    
        public static int getNum(ListNode head){ //获取链表节点个
        int num=0;
        while(head!=null){
            head=head.next;
            num++;
        }
            return num;
    }
}

方法三：用Set容器来判断

思路：
将链表1的节点全部存入Set，然后再遍历链表2，使用Set对象的contains方法判断即可。

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1==null&&pHead2==null){
            return null;
        }
        HashSet<ListNode> h=new HashSet<>();
        ListNode curr1=pHead1;
        while(curr1!=null){
            h.add(curr1);
            curr1=curr1.next;
        }
        ListNode curr2=pHead2;
        while(curr2!=null){  // while+if ！
            if(h.contains(curr2)){ //如果curr2.val在HashSet中存在即公共点
                return curr2;
            }
            curr2=curr2.next;
        }
        //无公共点，返回curr2=null
        return curr2;
    }
}