编程导航算法通关村第 1关 | 两个链表的第一个公共节点

**编程导航算法通关村第1关**

**题目描述**

给定两个单向链表，找到它们的第一个公共节点。

**输入**

* `headA`: 链表 A 的头结点* `headB`: 链表 B 的头结点**输出**

* 公共节点的值（如果存在）

**解决方案**

我们将使用两个指针分别遍历链表 A 和链表 B，直到找到公共节点。

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef findFirstCommonNode(headA, headB):
 # 如果链表 A 或链表 B 为 None，则返回 None if not headA or not headB:
 return None # 初始化两个指针，分别指向链表 A 和链表 B 的头结点 pA = headA pB = headB # 遍历链表 A 和链表 B，直到找到公共节点 while pA and pB:
 # 如果当前节点相同，则返回该节点的值 if pA == pB:
 return pA.val # 移动指针 pA = pA.next pB = pB.next # 如果没有找到公共节点，则返回 None return None# 示例代码if __name__ == "__main__":
 # 创建链表 A 和链表 B headA = ListNode(1)
 headA.next = ListNode(2)
 headA.next.next = ListNode(3)
 headB = ListNode(4)
 headB.next = ListNode(5)
 headB.next.next = ListNode(6)
 headB.next.next.next = ListNode(7)
 # 将链表 B 的最后一个节点指向链表 A 的第一个公共节点 headB.next.next.next.next = headA # 执行算法 result = findFirstCommonNode(headA, headB)
 if result:
 print("第一个公共节点的值为：", result)
 else:
 print("没有找到公共节点")