查找两个链表的第一个共同元素的Python程序

问题描述

给定两个单向链表，如何找到它们的第一个共同元素？

解题思路

可以使用双指针的方法，先遍历第一个链表，然后遍历第二个链表，如果遇到相同元素，则返回该元素。若遍历完两个链表都没有遇到相同元素，则返回 None。

具体实现可以用 Python 实现。首先，我们定义链表节点的类：

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

然后，我们定义一个函数来查找两个链表的第一个共同元素：

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

我们来分析一下这段代码的实现。

首先，我们定义两个指针 pA 和 pB，分别指向两个链表的头结点；
然后，我们遍历两个链表，如果遇到相同元素，则返回该元素；
如果遍历完两个链表都没有遇到相同元素，则返回 None。

代码实现

下面是完整的代码实现。注意：示例中使用了多个链表节点，这些节点的值都是随机生成的。

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

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


# 示例代码：

# 创建链表 a: 1->2->3->4->5
a = ListNode(1)
a.next = ListNode(2)
a.next.next = ListNode(3)
a.next.next.next = ListNode(4)
a.next.next.next.next = ListNode(5)

# 创建链表 b: 6->5->4->3->2->1
b = ListNode(6)
b.next = ListNode(5)
b.next.next = ListNode(4)
b.next.next.next = ListNode(3)
b.next.next.next.next = ListNode(2)
b.next.next.next.next.next = ListNode(1)

# 创建链表 c: 7->8->9
c = ListNode(7)
c.next = ListNode(8)
c.next.next = ListNode(9)

# 链表 a 和链表 b 的第一个共同元素是 5
a.next.next.next.next.next = b.next.next.next.next.next # 将 a 和 b 相交，指向的公共元素是 5
assert getIntersectionNode(a, b).val == 5

# 链表 a 和链表 c 没有共同元素
assert getIntersectionNode(a, c) == None