算法题学习 --- 两个链表的第一个公共结点
题目
描述
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
数据范围： 0n≤1000 要求：空间复杂度 O(1)，时间复杂度 O(n)
例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：
可以看到它们的第一个公共结点的结点值为 6，所以返回结点值为 6 的结点。
输入描述：
输入分为是 3 段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。 后台会将这 3 个参数组装为两个链表，并将这两个链表对应的头节点传入到函数 FindFirstCommonNode 里面，用户得到的输入只有 pHead1 和 pHead2。
返回值描述：
返回传入的 pHead1 和 pHead2 的第一个公共结点，后台会打印以该节点为头节点的链表。
示例 1
示例 2
分析
思路一---使用 vector 存储链表节点信息
这是比较容易想到的思路，我们使用 vector 存储其中一个链表的节点信息，然后遍历另一个链表，查找当前的节点是否在 vector 中，如果在，说明这是第一个相同的节点，我们直接返回该节点即可，否则等到遍历到链表末尾，返回 nullptr 即可。
但是，明显地，我们存储了 n 个节点的信息，这里的空间复杂度是 O(n),不符合题目的要求。
思路二---使用双指针法
我们先来考虑这样一种特殊的情况，如果两个链表的长度是相同的，且公共节点是第三个，那么我们分别遍历两个链表，那么一定会在第三个节点处相遇。
换言之，有公共节点的链表，它们的后半部分是完全相同的，区别只是前半部分的节点值不同，节点数量不同，上面的特殊情况中链表长度相同，所以我们从头开始遍历可以找到公共节点，那么我们的任务就是让两个遍历指针对齐。
我们可以事先遍历两个链表，得到两个链表的长度差 n，然后较长的链表遍历指针先走 n 步，此时，两个链表的遍历指针就如同遍历两个长度相同的链表了，一起向后遍历就可以找到第一个相同的节点了。如下：
step 1：单独的遍历两个链表，得到各自的长度。
step 2：求得两链表的长度差 n，其中较长的链表的指针从头先走 n 步。
step 3：两链表指针同步向后遍历，遇到第一个相同的节点就是第一个公共节点。
代码示例
版本一
事先占用了 O(n)的空间，在进行查找时，每遍历一个元素都需要查找一次 walkedListNode1，时间复杂度也达到了 O(mn)，这种思路比较容易想到，但消耗资源比较大。
版本二
注意 pQuick 指较长的链表，pSlow 指较短的链表，pQuick 需要提前走 abs(length1 - length2)步。
全程只使用了 pQuick 和 pSlow 两个指针，时间上也是 O(n)，遍历链表的时间。
版权声明: 本文为 InfoQ 作者【桑榆】的原创文章。
原文链接:【http://xie.infoq.cn/article/2ad66cce018e659bf8585df91】。文章转载请联系作者。
北海虽赊，扶摇可接；东隅已逝，桑榆非晚！ 2020-02-29 加入
Android手机厂商-相机软件系统工程师 爬山/徒步/Coding
评论