• 欢迎访问乐趣公园网站,WordPress信息,WordPress教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入乐趣公园 QQ群
  • Git主题现已支持滚动公告栏功能,兼容其他浏览器,看到的就是咯,在后台最新消息那里用li标签添加即可。
  • 最新版Git主题已支持说说碎语功能,可像添加文章一样直接添加说说,新建说说页面即可,最后重新保存固定连接,演示地址
  • 百度口碑求点赞啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊http://koubei.baidu.com/s/googlo.me
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏乐趣公园吧
  • 云落的淘宝店铺已经开张了哦,传送门:http://shop116317755.taobao.com

面试:如何判断两个链表相交及找到第一个相交点

常见算法 admin 125次浏览 0个评论

第一次遇到这个题目是在华为面试的时候遇到的,当时准备不充足,一上来有种懵逼的感觉,之后也想了几种方法,但空间复杂度还是有一些,回来一搜,发现果然又是漏点啊!

1.问题分析

看看两个链表相交到底是怎么回事吧,有这样的的几个事实:(假设链表中不存在环)

(1)一旦两个链表相交,那么两个链表中的节点一定有相同地址。

(2)一旦两个链表相交,那么两个链表从相交节点开始到尾节点一定都是相同的节点。

分析出来了问题的本质,那么思路也就自然有了。

2.问题解法

2.1 哈希解法:

既然连个链表一旦相交,相交节点一定有相同的内存地址,而不同的节点内存地址一定是不同的,那么不妨利用内存地址建立哈希表,如此通过判断两个链表中是否存在内存地址相同的节点判断两个链表是否相交。具体做法是:遍历第一个链表,并利用地址建立哈希表,遍历第二个链表,看看地址哈希值是否和第一个表中的节点地址值有相同即可判断两个链表是否相交。

时间复杂度O(length1 + length2)

空间复杂度O(length1)

分析:时间复杂度是线性的,可以接受,并且可以顺便找到第一个相交节点,但是却增加了O(length1)的空间复杂度,这显然不能令人满意。

2.2 问题转化

如果两个链表中存在相交节点,那么将第二个链表接到第一个链表的后面,然后从第二个链表的表头开始遍历,如果存在环,则遍历过程一定会回到链表二的表头节点。可是这种方法似乎并不能找到第一个相交节点。怎么办呢?怎样才能判断链表中是否存在环,并且找到环的开始节点呢?

网上看到了这样的一个解法:设置两个指针fast和slow,初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行头到尾部为NULL,则为无环链表),这样就可以判断两个链表是否相交了,程序如下:

bool IsExitsLoop(slist head)
{
slist fast = head;
while ( fast ->next )
{
slow ->next;
fast ->->next;
( slow fast )
      break  return (fast -> NULL);
}

下面看看怎么找环的入口,当fast与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n)。假设slow走了s步,则fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则:
2s = s + nr
s= nr
设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L – a
a = (n-1)r + (L – a – x)
(L – a – x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点(从相遇点向后遍历循环回到入口点的距离),于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇点为环入口点,也即为两个链表的第一个相同节点。程序描述如下:

slist* FindLoopPort(slist *head)
{
    slist *slow = head, *fast = head;
    while ( fast && fast->next ) 
    {
         slow = slow->next;
         fast = fast->next->next;
          ( slow == fast )  break (fast == NULL || fast->next == NULL)
        return NULL;
    slow = head;
    while (slow != fast)
    {
         slow = slow->next;
         fast = fast->next;
    }
    return slow;
}

这种解法似乎是非常犀利,逻辑推理很棒,但是这种解法的时间复杂度是怎么样的呢??slow每次前进一步,fast每次前进两步,这样的话遍历多少步会结束呢???(求人解释)

2.3 抓住要点

不妨遍历每个链表保存最后一个节点,看看最后一个节点是否是同一个节点,这种情况时间复杂度是O(length1 + length2)。基本也不需要什么空间,似乎是一个不错的想法哦,那么怎么找到第一个相交节点呢?可以遍历的过程中记录链表的长度L1和L2(假设L1>L2)这是遍历找到第一个链表中的第L1 – L2节点,然后链表一从第L1-L2个节点开始遍历,链表二从第一个节点遍历,每次前进一步,直到找到第一个相同的节点,则可以认为两个链表存在相交节点,并且该点即为第一个相交节点(原来这里写错了,感谢Ider指出这个错误)。这种解法的时间复杂度也是线性的,但是如果两个链表长度相差不多时,时间复杂度还是不错的。

到这里,我知道的几种典型的解法就说完了。欢迎大神们提供新的思路!!


乐趣公园 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明面试:如何判断两个链表相交及找到第一个相交点
喜欢 (1)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址