LeetCode-160-相交链表-Intersection-of-Two-Linked-Lists

jiezi

5 年前

爱写 Bug（ID：iCodeBugs）

编写一个程序，找到两个单链表相交的起始节点。

Write a program to find the node at which the intersection of two singly linked lists begins.

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8（注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：**

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2（注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：**

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。解释：这两个链表不相交，因此返回 null。

注意：

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

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

注意：长链表比短链表多出的长度是无需比较的

刚开始我是想着直接从两个链表末尾向前遍历对比节点是否相等，后面才看到是单链表。但是依然有很多的解题方法：

哈希表：把一个链表的节点先存储在哈希表，遍历另一个节点并判断该节点地址是否在哈希表中出现过如果出现过，输出该节点。需要占用额外空间 O(n)。

如果按要求在 O(1) 空间复杂度解题，最容易想到的就是：遍历链表得到链表长度，计算双链表差值，长链表减去差值得到的剩下的链表与短链表长度相等，然后开始比较地址。，当遇到第一个节点地址相同时即为所求。

这个原理简单，但是代码太冗长了，我们来看另一种更优雅的解法，看图帮助理解：

定义两个指针 curA、curB 分别从链表 A、B 开始遍历链表，此时最先遇到空节点 (到达末尾) 的链表即为短链表。

curA、curB 走过的长度均为 LenA。

此时将 curA 指向 链表 B (长链表)的头节点，curB 不变。两个指针开始第二段遍历，直到 curB 遇到空节点（长链表到达末尾）。

此时 curB 走完整个长链表，走的第二段长度就是差值 L。CurA 从长链表头节点开始，与 curB 同步，其走的第二段长度同样是差值 L。

此时 curA 在长链表剩余未遍历的节点长度是：LenB – L = LenA

此时将 curB 指向链表 A 的头节点，即将遍历链表 A 的长度为 LenA，则 curA、curB 剩余即将遍历的长度即为原本需要比较的长度。

开始第三段遍历，遇到第一个相同节点时返回即可。

Java：

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}
        ListNode curA = headA;
        ListNode curB = headB;
        while (curA != curB) {
            curA = curA == null ? headB : curA.next;
            curB = curB == null ? headA : curB.next;
        }
        return curA;
    }
}

Python：

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        curA , curB = headA , headB
        while curA != curB:
            curA = curA.next if curA else headB
            curB = curB.next if curB else headA
        return curA

欢迎关注公众号一起学习：爱写 Bug

LeetCode-160-相交链表-Intersection-of-Two-Linked-Lists

解题思路：

代码：