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

寻找两个链表的第一个公共节点，提供两种解法:解法1、使用哈希，把第一个链表的所有节点用哈希保存起来，之后进行第二个链表的扫描，如果第二个链表的某个节点的哈希映射冲突(在map中已经存在)，则该节点为第一个公共节点。空间复杂度O(max(m,n)),事件复杂度O(m+n)(有可能把两个链表都扫描完了)解法2、遍历两个链表，找出较长的那个链表，忽略较长链表的头部多出的一截（多出的一截不可能存在公共节点）然后依次对比节点是否相等，返回第一个节点相等的指针即可。空间复杂度O(1)事件复杂度O(m+n)(两个链表都进行了遍历，找出长度)

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//         解法一：
//         Map<ListNode,Integer> map = new HashMap<ListNode,Integer>();
//         while(pHead1!=null){
//             map.put(pHead1,pHead1.val);
//             pHead1 = pHead1.next;
//         }
//         while(pHead2!=null){
//             if(map.get(pHead2)!=null)return pHead2;
//             else pHead2 = pHead2.next;
//         }
//         return null;
//       解法二：    
        int len1 = 0;
        int len2 = 0;
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while(p1!=null){len1++;p1=p1.next;}
        while(p2!=null){len2++;p2=p2.next;}
        ListNode maxlist = len1>len2?pHead1:pHead2;
        ListNode minlist = len1>len2?pHead2:pHead1;
        int count =0;
        while(maxlist!=minlist){
            count++;
            if(count>Math.abs(len1-len2)){
                minlist = minlist.next;
            }
            maxlist = maxlist.next;
        }
        return maxlist;
    }
}

****