输入两个无环的单向链表,找出它们的第一个公共结点,假如没有公共节点则返回空。(注意由于传入数据是链表,以是错误测试数据的提示是用其他方式体现的,包管传入数据是准确的)
数据范围: n≤1000
要求:空间复杂度O(1),时间复杂度O(n)
比方,输入{1,2,3},{4,5},{6,7}时,两个无环的单向链表的结构如下图所示:
可以看到它们的第一个公共结点的结点值为6,以是返回结点值为6的结点。
输入形貌:
输入分为是3段,第一段是第一个链表的非公共部门,第二段是第二个链表的非公共部门,第三段是第一个链表和第二个链表的公共部门。 背景会将这3个参数组装为两个链表,并将这两个链表对应的头节点传入到函数FindFirstCommonNode内里,用户得到的输入只有pHead1和pHead2。
返回值形貌:
返回传入的pHead1和pHead2的第一个公共结点,背景会打印以该节点为头节点的链表。 |