第八课性能优化作业 - 判断合并链表

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也

可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，

如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元

素。

合并链表示意图

解答：两个链表之间要么存在公共的部分即在某个元素之后合并，要么不存在公共的部分。因为链表的长度和位置都是未知的，在分别给定链表头的情况下，暴力的解决方法是:遍历其中的一个链表所有节点并存储，然后用另一个链表中的节点去判断该链表中的节点是否存在与前一个链表节点中。

一种巧妙的方法是利用快慢指针的原理，在优先遍历某一个链表结束以后，从另一个链表的头开始遍历，如果两个链表有交集，那么两个遍历指针一定会在有共同元素的地方相遇。如果遍历指针在两个链表都遍历结束后仍然不相等，那么两个链表无公共部分。以上图为例，假设链表 1 的长度为：X+C；链表 2 的长度为 Y+C，C 为两个链表的公共部分，大于等于 0。则整个两个遍历指针遍历的过程分别为：X+C+Y+C 和 Y+C+X+C，因为 X+C+Y 恒等于 Y+C+X，所以会在 C 的位置相遇。如果 C>0 则两个遍历指针会在该处相遇（相等）链表有共同元素，如果 C=0 则两个遍历指针直到遍历结束也没有相遇（相等），即没有共同元素。

class Node:    def __init__(self,data,next=None):        self.data = data        self.next = next

class solution:    def get_intersectionNode(self,HeadA:Node,HeadB:Node):       l1 = HeadA       l2 = HeadB       if l1 is None or l2 is None:           return None       while(l1!=l2):           l1 = l1.next if l1.next else HeadB           l2 = l2.next if l2.next else HeadA           if l1 is None:               return l1       return l1