面试题 02.07. 链表相交

• 标签：哈希表、链表、双指针
• 难度：简单

题目链接

• 面试题 02.07. 链表相交 - 力扣

题目大意

给定两个链表的头节点 headA、headB。

要求：找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 None 。

比如：链表 A 为 [4, 1, 8, 4, 5]，链表 B 为 [5, 0, 1, 8, 4, 5]。则如下图所示，两个链表相交的起始节点为 8，则输出结果为 8。

解题思路

如果两个链表相交，那么从相交位置开始，到结束，必有一段等长且相同的节点。假设链表 A 的长度为 m、链表 B 的长度为 n，他们的相交序列有 k 个，则相交情况可以如下如所示：

现在问题是如何找到 m - k 或者 n - k 的位置。

考虑将链表 A 的末尾拼接上链表 B，链表 B 的末尾拼接上链表 A。

然后使用两个指针 pA 、pB，分别从链表 A、链表 B 的头节点开始遍历，如果走到共同的节点，则返回该节点。

否则走到两个链表末尾，返回 None。

代码

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if headA == None or headB == None:
            return None
        pA = headA
        pB = headB
        while pA != pB :
            pA = pA.next if pA != None else headB
            pB = pB.next if pB != None else headA
        return pA