架构师训练营第 8 周作业

 关注

发布于: 2020 年 08 月 01 日

作业一：以下两题，至少完成一道
有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。
﻿
﻿
解法一：
因为如果两个链表相交，则两个链表一定存在相同的结点。则遍历链表 A 并将每个结点的地址/引用存储在哈希表中。然后检查链表 B 中的每一个结点b_node。若在，则b_node为相交结点。时间复杂度为O(m+n), 空间复杂度为O(n)
﻿
				Set<ListNode> set = new HashSet<>();
        ListNode curA = headA , curB = headB;
        while(curA!=null||curB!=null){
            if(curA!=null){
                if(set.contains(curA)){
                    return curA;
                }
                set.add(curA);
                curA = curA.next;
            }
            if(curB!=null){
                if(set.contains(curB)){
                    return curB;
                }
                set.add(curB);
                curB = curB.next;
            }
        }
        return null;
﻿
解法二：双链表法
﻿
如果两个链表相交，那么相交点之后的长度是相同的。我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。为此，我们必须消除两个链表的长度差。算法步骤如下：
指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
如果 pA 到了末尾，则 pA = headB 继续遍历
如果 pB 到了末尾，则 pB = headA 继续遍历
比较长的链表指针指向较短链表head时，长度差就消除了。如此，只需要将最短链表遍历两次即可找到位置。空间复杂度 O(1)。 时间复杂度为 O(n)
﻿
  			if(headA==null||headB==null){
            return null;
        }
        ListNode pA = headA, pB = headB;
        while(pA!=pB){
            pA= pA==null? headB : pA.next;
            pB= pB==null? headA : pB.next;
        }
        return pA;
﻿

发布于: 2020 年 08 月 01 日阅读数: 22

坂田吴奇隆

 关注

还未添加个人签名 2019.01.06 加入

还未添加个人简介

发布

暂无评论

架构师训练营 第 8 周作业

作业一：

坂田吴奇隆

评论

架构师训练营第 8 周作业