判断两个单链表是否相交
问题:给两个单链表h1、h2,如何判断两个单链表是否相交?若相交,则找出第一个相交的节点。
解题思路:首先单链表的特点是,每一个结点都是由两个域 一个是data域、一个是 next指针域
相交的情况就是两条链表中有结点相同(即data域相等、next指针域也相等),而每一个结点只有一个next域,
所以一旦 两条链表相交,那么之后的链表就会是重合的情况,如下图所示呈现Y字形状:
解法一:第一直觉就是既然是两个链表寻找交点,双层循环遍历。
解法二:使用栈,根据最后两个链表最后相交的结点一定相同,只需要进行出栈判断(不会出现相交之后的部分长度不同的情况,因为单链表的定义里面既然相交的相交的后部分可以看做一个相同的链表的形式,两个链表只要有一个结点相交,后面就都相交)
解法三:使用链表长度截取到相同长度的时候进行比较
解法四:.哈希表法。
既然连个链表一旦相交,相交节点一定有相同的内存地址,而不同的节点内存地址一定是不同的,那么不妨利用内存地址建立哈希表,如此通过判断两个链表中是否存在内存地址相同的节点判断两个链表是否相交。具体做法是:遍历第一个链表,并利用地址建立哈希表,遍历第二个链表,看看地址哈希值是否和第一个表中的节点地址值有相同即可判断两个链表是否相交。
我们可以采用除留取余法构造哈希函数。
构造哈希表可以采用链地址法解决冲突。哈希表冲突指对key1 != key2,存在f(key1)=f(key2),链地址法就是把key1和key2作为节点放在同一个单链表中,这种表称为同义词子表,在哈希表中只存储同义词子表的头指针
时间复杂度O(length1 + length2)