LeetCode 160.相交链表(Python实现)

题目要求很简单，找到两个单链表相交的起始节点。
如下面图所示:

链表A、链表B在节点c1处相交，节点c1即为题目所求。
注意:

• 如果两个链表没有交点,返回null;
• 在返回结构后,两个链表仍须保持原有的结构;
• 可假定整个链表结构中没有循环;
• 程序尽量满足O(n)时间复杂度,且仅用O(1)内存.

题目解读:

1. 要注意程序的鲁棒性,特别是在树和链表类别的题目里,此题中要注意链表为空和链表不相交的两种特殊情况;
2. 不可随意修改链表的结构;
3. 题目要求尽量用满足O(n)时间复杂度,且仅用O(1)内存,我们可以以此分别讨论几种解法的质量.

字典法:

将链表A的节点地址存入字典中,然后在字典检索链表B的节点地址。如果有相同的,则表示找到了相交的节点。
这个方法简单且容易理解，但缺点在于要占用O(n)的辅助空间。

		#注意前面提到的鲁棒性,防止链表为空
        if not headA or headB:
            return None

        dic = {}
        #将节点地址作为字典的键
        while headA:
            dic[headA] = 1
            headA = headA.next
        while headB:
            if headB in dic:
                return headB
            headB = headB.next
        return None

集合法

与字典法同理，其数据载体由字典换为集合,同样要占用O(n)的辅助空间。

		if not headA or not headB:
            return None
        s = set()
        while headA:
            s.add(headA)
            headA = headA.next
        while headB:
            if headB in s:
                return headB
            headB = headB.next
        return None

长度比较法:

因为两链表从相交处开始相同，因此相交后的部分长度相同；
所以可以把两链表截取到相同的长度，同步进行两链表节点的比较。
如下图所示:
在计算出两链表的长度后 ,截取掉较长的一部分(b1)。然后上下链表逐个节点进行比较(a1与b2,a2与b3)，直到出现相交的节点c1。

        if not headA or not headB:
            return None

        lenA = self.getNodeLen(headA)
        lenB = self.getNodeLen(headB)
        if lenA <= lenB:
            for i in range(lenB - lenA):
                headB = headB.next
        else:
            for i in range(lenA - lenB):
                headA = headA.next
        while headA != headB:
            headA, headB = headA.next, headB.next
        return headA

    def getNodeLen(self, node):
        length = 0
        while node:
            length += 1
            node = node.next
        return length

指针追逐法:

接下来这种解法,是我个人认为几种解法中最优雅的:
p,q分别为headA,headB的指针，指针在两链表的长度上追逐。
若p,q同时达到地址相同的节点，返回p，q任一；
若没有相同的节点，各自走了两链表的长度，返回None。

		p, q = headA, headB
        if not p or not q: return None
        while p != q:
           p = p.next if p else headB
           q = q.next if q else headA
        return p

我们可以举一个具体的例子,假设题目给的两链表分别为listA = [4, 1, 8, 4, 5], listB = [5, 0, 1, 8, 4, 5]。图解如下:

然后我们进行追逐,因为存在长度差,所以p与q之间总存在一定的差距。
当p行至链表A的尾时,下一步就是链表B的头;同理q行至链表B的尾时,下一步也为链表A头。这种方式变相地消除了两者的距离差。

不难看出,在上图基础上,再往后3步,p,q便能同时指向相交节点。
要是两个链表没有相交的节点,p == q == NULL退出(再次强调鲁棒性)。

这里有人可能要问: 为什么相交节点不是1而是8?

这也是本题的一个巧妙之处,还记得我们第一种方法存储的是节点的地址而不是节点的val吗?
原因就在这里,两个节点的val相同并不代表他们在内存中的地址相同,也可以说,他们前一个节点的指针分别指向了不同的节点。