求两单链表交点

56 阅读 0 评论 37 点赞

我是靠谱客的博主单身小土豆，最近开发中收集的这篇文章主要介绍求两单链表交点，觉得挺不错的，现在分享给大家，希望可以做个参考。

题目:已知两单链表有交点，给出两单链表的头指针，求交点位置。

思路①：自交点至公共尾部的结点都是相同的，则分别遍历两个链表，并将每个结点的指针分别存储在两个数组中，然后从两数组尾部开始比较，到两指针值开始不同时，前一位置即使指向交点的指针。

思路②：分别遍历两链表，得到各自的长度L1、L2，然后长的减短的得L；再从头结点开始，长链表的头指针先向前走L步，然后两指针同步单步往前走，指向相同结点时即是交点。此方法不需额外的存储空间。

思路③：先遍历一个单链表到尾部，然后将尾部的空指针指向另一个单链表的头部，转化为求带环单链表的连接点的问题。解决方法参考：http://blog.sina.com.cn/s/blog_725dd1010100tqwp.html

参考资料：《剑指offer》

以上就是单身小土豆为你收集整理的求两单链表交点的全部内容，希望文章能够帮你解决求两单链表交点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。