架构师训练营 W8 作业

关注

发布于: 2020 年 07 月 26 日

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。
﻿
Python3 Solution
def getIntersectionNode(self, A: ListNode, B: ListNode):
        if not A or not B:
            return None
        l1 = self.get_length(A)
        l2 = self.get_length(B)
        if l1 < l2:
            extra = l2 - l1
            while extra:
                B = B.next
                extra -= 1
        else:
            extra = l1 - l2
            while extra:
                A = A.next
                extra -= 1
        while A and A != B:
            A = A.next
            B = B.next
        return A
    
    def get_length(self, head):
        ans = 0
        while head:
            ans +=1 
            head = head.next
        return ans
        
如果返回的 A 为 None，则无交点，否则即为交点。

发布于: 2020 年 07 月 26 日阅读数: 61

原文链接:【http://xie.infoq.cn/article/711f2e133bb06ae50b4b65eaa】。未经作者许可，禁止转载。

Kun

关注

Life is short. 2018.01.13 加入

Software Developer

发布

暂无评论

创作场景

架构师训练营 W8 作业

Kun

评论