看动画，拿 Offer：大厂算法面试真题全解析( 五 ) _链表

至此，方法 1 的思路与实现就讲完了。利用 set 来判断重复的地址时，由于 set 利用红黑树实现，在 set 集合中查找与添加一个元素的时间复杂度为 O(logN) 。所以算法的整体时间复杂度是 O(NlogN) ，由于我们需要把所有的地址都通过 set 存储，所以空间复杂度为 O(N) 。
下面我们介绍双指针计算法。
使得时间复杂度优化为 O(N) ，空间复杂度优化为 O(1) 。我们发现，在两个链表相交后，有一段共享的链表，并且长链表比短链表多出一些结点。在找相交节点的时候，可以首先排除掉长链表多出的结点，这时两个链表的长度就相同了。
然后再通过两个指针同时用相同速度扫描两个链表，当找到同一个节点时即为两个链表的交点了。
具体来说，首先通过指针遍历链表，计算链表 A 和链表 B 的长度，相减得出较长的链表多出的节点个数 count 。例如，链表 A 的长度为 5 ，链表 B 的长度为 6 ，链表 B 比链表 A 多出了 1 个节点，然后将较长链表的头结点指针向前移动 count 个节点，也就是将较长链表指针移动到和较短链表头结点对齐的位置。
例如，计算出长链表比短链表多出 1 个节点，所以将 headB 向后移动 1 个节点，最后将 headA 与 headB 同时向前移动，当两指针指向同一个节点时，就找到了两链表的相交节点，将该节点地址返回，如果没有交点则返回 NULL 。
例如，当 headA 与 headB 移动到节点 8 时，两个指针值相同，即找到了两个链表的相交节点，我们将该地址返回。
首先开发计算链表的长度函数。
函数参数为待求长度的链表头结点指针 head ，设置存储链表长度，通过 while 循环，每遍历一个节点， ++ ，最后函数返回链表的长度，然后开发，移动较长链表头结点指针的函数，函数传入链表头结点指针 head 与移动的节点数 count ，通过 for 循环，将 head 指针向前移动 count 个节点，函数返回移动后的指针 head 。
最后来看主体代码的开发。
首先计算链表 A 与链表 B 的长度，分别存储至与。然后使用 if 语句比较与的大小，通过函数，移动较长链表的头结点，使指针 headA 与 headB 对齐，最后求两个链表的交点，设置存储交点地址。通过 while 循环，同时向前移动 headA 与 headB ，当 headA 与 headB 相等时，该节点即为两链表的交点，将它的地址存储至，并跳出循环，函数最终返回，两个链表的交点地址。
最后我们开发 main 函数测试程序接口。程序中设置了样例中的 8 个节点 a、b、c、d、e、f、g、h ，链表 a、b 与链表 c、d、e 相交于节点 f ，调用函数，求出两链表的交点地址。
提交，题目通过测试， 160 相交链表这道题目就讲完了。
两个排序链表的合并（ 21）链表划分（ 86）链表中的环的入口节点（ 142）使用栈实现队列（ 232）包含 min 函数的栈（ 155）合法的出栈序列（ 946）分糖果（ 455）射击气球（ 452）移除 K 个数字（ 402）跳跃游戏（ 55）求子集（ 78）生成括号（ 22）N 皇后（ 51）火柴棍摆正方形（ 473）路径总和 II （ 113）最近的公共祖先（ 236）二叉树转链表（ 114）侧面观察二叉树（ 199）数组转二叉查找树（ 108）二叉查找树的转换（ 538）二叉查找树的节点删除（ 450）插入位置（ 35）区间查找（ 34）旋转数组查找（ 33）最长回文串（ 409）词语模式（ 290）重复的 DNA 序列（ 187）打家劫舍（ 198）三角形（ 120）连续的最大字段和（ 53）找零钱（ 322）课程表（ 207）进击的骑士（ 1197）岛屿数量（ 200）