如何使用Python实现链表的求交集（Intersection）操作

2023-04-11 00:00:00 交集 链表 如何使用

链表的交集操作可以用两种方法实现：

方法一：暴力枚举。对于链表 A 中的每个节点，依次遍历链表 B，找到相同值的节点，加入到结果链表中。时间复杂度为 O(mn)，其中 m、n 分别为链表 A、B 的长度。

方法二：使用哈希表。遍历链表 A，将每个节点的值存入哈希表中。遍历链表 B，对于每个节点的值，判断其是否在哈希表中出现，如果出现则加入结果链表中。时间复杂度为 O(m+n)，空间复杂度为 O(m) 或 O(n)，取决于哪个链表的长度更短。

下面演示使用哈希表实现链表的交集操作的代码：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    node_set = set()
    # 遍历链表 A，将每个节点的值存入哈希表中
    while headA:
        node_set.add(headA)
        headA = headA.next
    # 遍历链表 B，对于每个节点的值，
    # 判断其是否在哈希表中出现，如果出现则加入结果链表中
    while headB:
        if headB in node_set:
            return headB
        headB = headB.next
    return None

调用 getIntersectionNode 函数，传入两个链表的头节点，并返回交集节点的值。例如：

# 创建链表 A，值为 pidancode.com -> 1 -> 2 -> 3
headA = ListNode("pidancode.com")
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
headA.next = node1
node1.next = node2
node2.next = node3

# 创建链表 B，值为 2 -> 3 -> 4 -> 5
headB = ListNode(2)
node4 = ListNode(3)
node5 = ListNode(4)
node6 = ListNode(5)
headB.next = node4
node4.next = node5
node5.next = node6

# 计算链表 A 和链表 B 的交集
intersection = getIntersectionNode(headA, headB)
if intersection:
    print(intersection.val)
else:
    print("无交集")

输出结果为：

2

说明链表 A 和链表 B 在值为 2 的节点处相交。

相关文章