leetcode_相交链表
2018-06-05 本文已影响0人
壹叶壹
编写一个程序，找到两个单链表相交的起始节点。
例如，下面的两个链表：
在节点 c1 开始相交。
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
我的思路：由于相交链表后面的长度都是一样的，所以当减去长链表前面多出的一部分，我们就可以直接同步调遍历两个链表，找到两个链表一样的节点即可；
代码实现：
更高效简介的代码：
这份代码时提交中耗时最少的，其本质思想是一样的，都是先将长链表遍历到与短链表相同的长度，再查找两者相同的节点。但是其在长链表消减时更加精巧，他先将两个链表都往后遍历，直到有一个链表遍历完了，此时未遍历完的链表后面剩的节点数就是其相对于短链表多的节点数。这时候，当前节点向后移动一个，其头节点就向后移动一个，当遍历完时。两个链表的长度就相同了；
咯咯咯
