两个链表

有如下的两个链表1和2，检测链表有没有合并，如果有合并指出链表的值。

算法简述

合并到意思是两个链表当前指针的下一个节点的地址相同。那最直观的方法就是已最小表为基准表，遍历该基准表，并判断另一个表中是否有节点的指针指向基准表的当前节点，直到基准表遍历结束，这种方法的时间复杂度式O(n^2)，准确的说应该是O(n * m)。

p = 链表1头指针;
q = 链表2头指针;
q = min{p,q}; // 选取最小链表
while(q.next != null){
    while(p.next != null){
        if(p.next == q){
            return q.data;
        }else{
    	      p = p.next;
        }
    }
    p = 链表1头指针;
    q = q.next;
}
return 0;

分析

有没有更快的处理方式了呢？

改进

1. 先遍历一遍最大的链表，并且组织一个Map<Node.next,Node.data>;

2. 然后再遍历小的链表，并通过map查询是否存在Key即可，存在即说明有合并，不存在说明没有合并；

3. 时间复杂度 = O（n）。