跳至主要內容

面试题 02.07. 链表相交

ITCharge大约 1 分钟

面试题 02.07. 链表相交open in new window

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

题目链接

题目大意

给定两个链表的头节点 headAheadB

要求:找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 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

然后使用两个指针 pApB,分别从链表 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