欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数字之魅:判断两个链表是否相交

程序员文章站 2022-06-24 20:46:06
题目:给出两个链表的头指针,比如head1和head2,判断这两个链表是否相交。这里为了化简,我们假设两个链表均不带环。 方案一:蛮力法。一般我们都能想到的,就是从head1开始,逐个与head2中...

题目:给出两个链表的头指针,比如head1和head2,判断这两个链表是否相交。这里为了化简,我们假设两个链表均不带环。

方案一:蛮力法。一般我们都能想到的,就是从head1开始,逐个与head2中的每个结点的地址比较,看是否相等,如果不等,则head1移动到下一个结点,继续和head2中的每一个结点的地址比较;如果找到相等,则这两个链表相交;直到head1==null,则不相交。注意为了避免存在相同的元素,我们采取比较地址的方法,而不是比较元素,在判断链表里是否有环的时候,也是采用比较地址的方法。时间复杂度为o(n*n)。

方案二:利用空间换时间的做法。采用计数法。如果两个链表相交则说明该链表有相同的结点。而地址有时其唯一的标示,所以我们还是可以采取和方案一一样的比较地址的方案。只不过我们使用哈希表,将链表head1每个结点的地址进行hash取值,然后遍历haed2链表一遍,我们就可以得出是否有相同的结点,也就是是否存在相交。这里是时间复杂度为:o(n)=o(lenght(head1)+length(head2))+辅助空间o(lenght(head1))。

方案三:由于链表里没有环。那么我们可以将该问题进行转化,将head1头结点接到head2的尾部,这样我们就可以通过判断head2链表里有没有环来进行判断,他们是否相交。具体如下图所示。

如果head2没有环,则证明这两个链表不相交,如果head2里有环,则证明这两个链表相交。

具体如何判断链表是否有环。

方案四:由于只需要判断这两个链表时否相交,如果相交,那么这两个链表的最后一个结点一定是同一个,它们是‘y’字形的;但是如果不相交那就不存在这个特点。所以我们可以通过两次遍历,得到两个链表的最后一个结点,然后通过比较这两个链表的地址是否相同来判断它们是否相交。时间复杂度:o(lenght(head1)+length(head2))=o(n)。

 

数字之魅:判断两个链表是否相交

 

这个题虽然比较简单,只是方案三里有一点儿值得学习的地方,就是我们可以将不熟悉的问题转化为我们熟悉的问题,这样在解决问题的时候就会简单很多。有些问题正面解决很难,但是通过转化以后就会很简单。