Python 中两个链表的交集

假设我们有两个链表 A 和 B，这些链表中含有一些元素。我们需要返回交集元素的引用。输入为 intersectionVal = 8，A = [4,1,8,4,5]，B = [5,0,1,8,4,5]，skipA = 2 和 skipB = 3，这些用于从 A 中跳过 2 个元素，从 B 中跳过 3 个元素。

为了解决此问题，我们将按照以下步骤操作：

  • 定义一个名为 d 的映射
  • 在 headA 不为空时
    • d[headA] := 1
    • headA := headA 的下一个
  • 在 headB 不为空时
    • 如果 headB 在 d 中
      • 返回 headB
    • headB := headB 的下一个
  • 返回 null

示例

让我们看看以下实现以获得更好的理解：

 实时演示

class ListNode:
   def __init__(self, data, next = None):
      self.data = data
      self.next = next
class Solution(object):
   def getIntersectionNode(self, headA, headB):
      """
      :type head1, head1: ListNode
      :rtype: ListNode
      """
      dict = {}
      while headA:
         dict[headA]=1
         headA = headA.next
      while headB:
         if headB in dict:
            return headB
         headB = headB.next
      return None
headA = ListNode(4)
headB = ListNode(5)
Intersect = ListNode(8, ListNode(4, ListNode(5)))
headA.next = ListNode(1, Intersect)
headB.next = ListNode(0, ListNode(1, Intersect))
ob1 = Solution()
op = ob1.getIntersectionNode(headA, headB)
print("Intersection:",op.data)

输入

headA = ListNode(4)
headB = ListNode(5)
Intersect = ListNode(8, ListNode(4, ListNode(5)))
headA.next = ListNode(1, Intersect)
headB.next = ListNode(0, ListNode(1, Intersect))

输出

Intersected at '8'

更新于：2020 年 4 月 28 日

972 次观看

开启您的职业生涯

完成课程，获得认证

立即开始
广告