两个链表找第一个公共节点

83 阅读 0 评论 55 点赞

我是靠谱客的博主不安蜗牛，最近开发中收集的这篇文章主要介绍两个链表找第一个公共节点，觉得挺不错的，现在分享给大家，希望可以做个参考。

题目：输入两个链表，找出它们的第一个公共结点

思想：设两个链表分别为p,q.将p拼接到q之后，将q拼接到p之后，得到两个新的等长链表p1,q1.在从头至尾依次对比两链表结点

第一个相等的点即为所要找的结点

for examp：p= 1234 q= 98764

拼接之后为：p1=123498764

q1=987641234 两个链表指针依次对比，可以很直观的看出来第一个结点为4

小注: 王道《数据结构》链表课后习题也有类似的题目，只不过他找的是共同后缀的第一个结点。

算法思想：分别从头到尾遍历，得到p与q的长度，算出长度之差为h，让长的链表的指针先走h个结点，在比较两个链表的指针

若不同，两指针分别指向后一个结点，直至找到相同结点为止，返回结点。

以上就是不安蜗牛为你收集整理的两个链表找第一个公共节点的全部内容，希望文章能够帮你解决两个链表找第一个公共节点所遇到的程序开发问题。

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

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