基本思路1:
链表1,2均没有环
把链表1首尾相连,判断链表2是否有环,若有环,则相交。
基本思路2:
遍遍历链表1,2,若尾指针相等,则相交。
如何就交点:
链表1和链表2的长度想减求绝对值,较长的链表先移动差值个位置,然后两个链表同时移动,相等的地方即为交点。
算法也不给出了
假定有两个字符串str1和str2,那么如何判断str1和str2两个字符串相等?if(str1 == str2){...}?
首先指出,在java中,不能用“==”和“!=”来判断两个字符串是否相等。因为String是引用类型,而不是基本数据类型。故它们的比较是使用地址和值(相当于C中的指针)来比较,因为它们是不同的对象,有不同的地址。故str1==str2永远是false,而str1!=str2永远都是true。
解决方法:
if("".equals(editText.getText().toString().trim())){ }
向set中添加的元素类型必须重载<操作符用来排序。排序满足以下准则:
1、非对称,若A<B为真,则B<A为假。
2、可传递,若A<B,B<C,则A<C。
3、A<A永远为假。
set中判断元素是否相等:
if(!(A<B || B<A)),当A<B和B<A都为假时,它们相等。以上好处可以直接不通过指针而通过对象来查找
http://www.cnblogs.com/Clingingboy/p/3252136.html
http://bbs.csdn.net/topics/390237400
基本思路1:
链表1,2均没有环
把链表1首尾相连,判断链表2是否有环,若有环,则相交。
基本思路2:
遍遍历链表1,2,若尾指针相等,则相交。
如何就交点:
链表1和链表2的长度想减求绝对值,较长的链表先移动差值个位置,然后两个链表同时移动,相等的地方即为交点。
算法也不给出了
转载于:https://www.cnblogs.com/GoAhead/archive/2012/05/23/2514320.html
问题:给两个单链表h1、h2,如何判断两个单链表是否相交?若相交,则找出第一个相交的节点。
解题思路:首先单链表的特点是,每一个结点都是由两个域 一个是data域、一个是 next指针域
相交的情况就是两条链表中有结点相同(即data域相等、next指针域也相等),而每一个结点只有一个next域,
所以一旦 两条链表相交,那么之后的链表就会是重合的情况,如下图所示呈现Y字形状:
解法一:第一直觉就是既然是两个链表寻找交点,双层循环遍历。
解法二:使用栈,根据最后两个链表最后相交的结点一定相同,只需要进行出栈判断(不会出现相交之后的部分长度不同的情况,因为单链表的定义里面既然相交的相交的后部分可以看做一个相同的链表的形式,两个链表只要有一个结点相交,后面就都相交)
解法三:使用链表长度截取到相同长度的时候进行比较
解法四:.哈希表法。
既然连个链表一旦相交,相交节点一定有相同的内存地址,而不同的节点内存地址一定是不同的,那么不妨利用内存地址建立哈希表,如此通过判断两个链表中是否存在内存地址相同的节点判断两个链表是否相交。具体做法是:遍历第一个链表,并利用地址建立哈希表,遍历第二个链表,看看地址哈希值是否和第一个表中的节点地址值有相同即可判断两个链表是否相交。
我们可以采用除留取余法构造哈希函数。
构造哈希表可以采用链地址法解决冲突。哈希表冲突指对key1 != key2,存在f(key1)=f(key2),链地址法就是把key1和key2作为节点放在同一个单链表中,这种表称为同义词子表,在哈希表中只存储同义词子表的头指针
时间复杂度O(length1 + length2)