[编程题]两个链表的第一个公共结点

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

    ListNode(int val) {
        this.val = val;
    }
}*/
/*
方法一利用hashmap
import java.util.HashMap;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        //定义两个指针
        if(pHead1==null||pHead2==null){
            return null;
        }
        ListNode p1=pHead1;
        ListNode p2=pHead2;
        HashMap<ListNode,Integer> hash=new HashMap<ListNode,Integer>();
        while(p1!=null){
            hash.put(p1,null);
            p1=p1.next;
        }
        ListNode result=null;
        while(p2!=null){
            if(hash.containsKey(p2)){
                result=p2;
                //结束整个循环
                break;
            }
            p2=p2.next;
        }
        return result;

    }
}*/


//方法二先计算两个链表的长度，如果有公共结点，则公共结点之后所有的结点都是公共结点
//因为每个链表只能有一个指针
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        //定义两个指针
        if(pHead1==null||pHead2==null){
            return null;
        }
        ListNode p1=pHead1;
        ListNode p2=pHead2;
        //计算两个链表的长度
        int lengthOfpHead1=0;
        int lengthOfpHead2=0;
        while(p1!=null){
            lengthOfpHead1++;
            p1=p1.next;
        }
           while(p2!=null){
            lengthOfpHead2++;
            p2=p2.next;
        }
  //因为上面求取长度时两个指针都位于末尾了，防止java.lang.NullPointerException**
      //p1与p2必须重新赋值**
        p1=pHead1;
        p2=pHead2;
        int differLength=lengthOfpHead1-lengthOfpHead2;
         ListNode result=null;
        if(differLength>=0){
            while(differLength>0){
                p1=p1.next;
                --differLength;
            }
            while(p2!=null){
                if (p1.next==null&&p2.next==null){
                result=null;
            }
                if(p1==p2){
                    result=p2;
                    break;
                }
                p1=p1.next;
                p2=p2.next;
            }
        }else{
                while(differLength<0){
                p2=p2.next;
                ++differLength;
            }
            while(p1!=null){
           if (p1.next==null&&p2.next==null){
                result=null;
            }
                if(p1==p2){
                    result=p1;
                    break;
                }
                p1=p1.next;
                p2=p2.next;
            }
        }
        return result;
    }
}