• 如何判断两个非空单向链表是否相交
  • 发布于 1个月前
  • 39 热度
    0 评论
题目:如何判断两个非空单向链表是否相交,如果相交返回该公共结点的地址,否则返回NULL。

1.首先应该想出两个链表怎样才能有公共结点(公共结点的位置可能出现在哪)。

· i> 头部:是不可能的,因为如果两个头指针指向同一个头结点即就是两个指针指向一个链表,题中说明是两个链表,不符题意;
· ii> 中间:也是不可行的,因为是单向非空链表,结点的next域只能存放一个结点的地址;
· iii> 尾部:是可行的,如下图:

2.分析求解思路:
 
i>思路一: 分别统计两个链表结点个数

如果结点个数相同则用两个指针分别从头指针开始跑,直至两指针指向同一结点,返回地址;
如果结点个数不同则先用一个指针跑到自己合适的位置,然后两个指针一起跑直至指向同一结点,返回地址;如果找不到即返回NULL。

代码实现截图如下:

但是在本代码后面的部分写的不好,可以进行如下优化:

这段代码实现了上一个代码的优化,让n减为0,来使p1指到恰当的位置上;然后是p1等于p2在第二个for循环中作为结束条件,最后直接返回p1,这样做的好处是:
p1是指向长链表,如果存在公共结点则返回p1所指结点的地址,如果不存在公共结点即就是p1跑到NULL,同样是返回p1(这里p1为NULL),合并为一个return,使代码变为单出口。
 
ii> 思路二:用两个动态数组分别保存结点的地址

如果存在公共结点则说明在跑到某个地方时,两个数组的地址值相等了即找到了公共结点,返回地址值;如果遍历完两个数组都没有找到相同的地址值,就说明没有公共结点,返回NULL。

代码实现截图如下:

比较两种思路:

a.第一种的思路时间复杂度为o(n),第二种的时间复杂度为o(n^2);
b.第一种更容易理解和接受

以上两段代码是核心代码,下面附上创建链表和调用和运行结果的截图供大家参考:

创建链表相关实现:

第一个函数是创建链表,第二个函数为构建新的链表使之成为具有公共结点的链表;
01第一个验证:两个链表分别为h1指向的数据值: 10,20,30,40,50,60; h2指向的数据值为11,22,50,60;截图如下:

02第二个验证:两个链表分别为h1指向的数据值:10,20,30,40,50,60;h2指向的数据值:11,22;截图如下:

看完了,如果还有什么疑问,留言分享吧~
用户评论