leetcode_相交链表

编写一个程序,找到两个单链表相交的起始节点。

例如,下面的两个链表:


在节点 c1 开始相交。


注意:

如果两个链表没有交点,返回 null.

在返回结果后,两个链表仍须保持原有的结构。

可假定整个链表结构中没有循环。

程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

我的思路:由于相交链表后面的长度都是一样的,所以当减去长链表前面多出的一部分,我们就可以直接同步调遍历两个链表,找到两个链表一样的节点即可;

代码实现:

更高效简介的代码:

这份代码时提交中耗时最少的,其本质思想是一样的,都是先将长链表遍历到与短链表相同的长度,再查找两者相同的节点。但是其在长链表消减时更加精巧,他先将两个链表都往后遍历,直到有一个链表遍历完了,此时未遍历完的链表后面剩的节点数就是其相对于短链表多的节点数。这时候,当前节点向后移动一个,其头节点就向后移动一个,当遍历完时。两个链表的长度就相同了;

                                                                 咯咯咯

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 搞懂单链表常见面试题 Hello 继上次的 搞懂基本排序算法,这个一星期,我总结了,我所学习和思考的单链表基础知识...
    醒着的码者阅读 4,653评论 1 45
  • 单链表 单链表问题与思路 找出单链表的倒数第K个元素(仅允许遍历一遍链表)使用指针追赶的方法。定义两个指针fast...
    wxkkkkk阅读 620评论 0 0
  • 链表删除[203] Remove Linked List Elements[19] Remove Nth Node...
    野狗子嗷嗷嗷阅读 6,352评论 4 35
  • 链表问题是面试过程中经常被问到的一部分,很考查编程功底。最近刷了 LeetCode 上链表部分的面试题,我总结了一...
    JohnnyShieh阅读 5,008评论 0 9
  • 法国电影“闻香识女人”中,失明生活使得弗兰克上校对听觉和嗅觉异常敏感,甚至能靠闻对方的香水味道识别其身高、发色乃至...
    秋水不语阅读 476评论 0 1