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

解法1

运用一个map 存储第一个链表的所有结点，然后遍历第二个链表 看结点是否存在key中

代码

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

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.HashMap;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        HashMap map = new HashMap<>();
        while(pHead1!=null){
            map.put(pHead1,null);
            pHead1 = pHead1.next;
        }
        while(pHead2!=null){
            if(map.containsKey(pHead2)){
                return pHead2;
            }
            pHead2 = pHead2.next;
        }
        return null;
    }
}

解法2

把两个链表变成等长的链表就很好判断了。

代码

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
         ListNode p = pHead1;
         ListNode q = pHead2;
         while(p!=q){
             p = p!=null ? p.next:pHead2;
             q = q!=null ? q.next : pHead1;
         }
        return q;
    }
}