在Python中查找两个链表的交点的程序

在解决编程问题的过程中，我们经常需要找到两个链表的交点。这个问题可以在Python中比较轻松地解决。本文将介绍两种方法，分别是“双指针法”和“Hash表法”。

更多Python相关文章，请阅读：Python 教程

双指针法

双指针法是一种解决链表相关问题的常见方法。它的思路是使用两个指针，一个指针遍历链表A，另一个指针遍历链表B，当两个指针指向的节点相同时，就找到了交点。

以下是实现这个算法的Python代码：

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

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    if not headA or not headB:
        return None

    pA, pB = headA, headB
    while pA != pB:
        pA = headB if not pA else pA.next
        pB = headA if not pB else pB.next

    return pA

在这个代码中，我们定义了一个“ListNode”类，表示链表的节点。它有两个属性：值（val）和下一个节点（next）。

函数“getIntersectionNode”接受两个链表的头节点“headA”和“headB”，并返回它们的交点。首先，我们判断两个链表是否为空。如果有一个为空，那么它们肯定没有交点，可以直接返回None。然后，我们定义两个指针pA和pB，分别指向链表A和B的头节点。接着，我们循环检查pA和pB所指向的节点是否相等，如果相等，那么就找到了交点，返回pA或pB都可以。如果pA和pB都不为空，那么它们一定会在某个时刻相等，因为它们都会遍历链表A和B中的所有节点。如果有一个为空，那么这个指针就会跳到另一个链表的头节点，继续遍历。最后，如果两个指针都到达了链表的末尾，还没有找到交点，就返回None。

下面是一个测试样例：

# 创建链表A
A1 = ListNode(1)
A2 = ListNode(2)
A3 = ListNode(3)
A4 = ListNode(4)
A5 = ListNode(5)
A1.next = A2
A2.next = A3
A3.next = A4
A4.next = A5

# 创建链表B
B1 = ListNode(10)
B2 = ListNode(9)
B3 = ListNode(8)
B1.next = B2
B2.next = B3
B3.next = A3

# 查找交点
result = getIntersectionNode(A1, B1)
print(result.val) # 输出：3

在这个测试中，我们先创建了两个链表A和B，链表A包含5个节点，链表B包含3个节点，其中节点3是它们的交点。我们调用函数“getIntersectionNode”传入链表A和B，它会返回交点节点A3。最后，我们输出它的值3。

Hash表法

另一种查找两个链表交点的方法是使用“Hash表法”。这种方法的思路是，首先遍历链表A，并将每个节点地址存入一个集合中。然后遍历链表B，对于每个节点，在集合中查找是否有相同地址的节点，如果找到了，那么就找到了它们的交点。

以下是实现这个算法的Python代码：

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    visited = set()
    pA, pB = headA,headB
    while pA:
        visited.add(pA)
        pA = pA.next
    while pB:
        if pB in visited:
            return pB
        pB = pB.next
    return None

这个代码与双指针法的代码相比，多了一个“visited”集合。它用于存储链表A的所有节点地址。我们遍历链表A，将所有节点地址添加到集合中。然后，我们遍历链表B，对于每个节点，都在集合中查找是否有相同地址的节点。如果找到了，那么就找到了交点，返回它；否则，返回None。

下面是一个测试样例：

# 创建链表A
A1 = ListNode(1)
A2 = ListNode(2)
A3 = ListNode(3)
A4 = ListNode(4)
A5 = ListNode(5)
A1.next = A2
A2.next = A3
A3.next = A4
A4.next = A5

# 创建链表B
B1 = ListNode(10)
B2 = ListNode(9)
B3 = ListNode(8)
B1.next = B2
B2.next = B3
B3.next = A3

# 查找交点
result = getIntersectionNode(A1, B1)
print(result.val) # 输出：3

在这个测试中，我们与上述测试一样，调用函数“getIntersectionNode”传入链表A和B，它会返回交点节点A3。最后，我们输出它的值3。