判断两个单向链表是否合并





1. 暴力解法

    从头开始遍历一个链表，遍历第一个链表中的每个节点时，同时从头到尾遍历第二个链表，看是否有相同的节点，第一次找到相同的节点即第一个交点；若遍历结束未找到相同的节点，即不存在交点，时间复杂度为O(n^2)



1. 哈希表法

    既然连个链表一旦相交，相交节点一定有相同的内存地址，而不同的节点内存地址一定是不同的，那么不妨利用内存地址建立哈希表，如此通过判断两个链表中是否存在内存地址相同的节点判断两个链表是否相交。具体做法是：遍历第一个链表，并利用地址建立哈希表，遍历第二个链表，看看地址哈希值是否和第一个表中的节点地址值有相同即可判断两个链表是否相交。时间复杂度O(length1 + length2)