文档章节

IT公司100题-7-判断两个链表是否相交

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2015/11/04 11:42
字数 722
阅读 72
收藏 4

问题描述:

有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。 

  1. 如何判断一个链表是不是这类链表? 

问题扩展: 

  1. 如果链表可能有环呢?

  2. 如果需要求出两个链表相交的第一个节点呢? 

问题分析:

在无环的情况下,如果两个链表有结点相同,那么它们下一结点也相同,如此可推出尾结点也相同。 

那么只要判断两链表的尾结点是否相同。(O(len1+len2))

//if there is no cycle
boolean isJoinedSimple(Node n1, Node n2){
   while(n1 != null)
      n1 = n1.next;
   while(n2 != null)
      n2 = n2.next;
   return n1 == n2;
}

扩展1:

需要先判断有环无环,可以这样做,定义两个指针,指向头结点,一个每次移动一个结点,另一个每次移动两个结点,如果慢的能追上快的(也就是两个指针重逢),就说明有环。

boolean hasLoop(Node n){
   Node nFast = n;
   Node nSlow = n;
   while(nFast != null && nSlow != null){
      nFast = nFast.next.next;
      nSlow = nSlow.next;
      if(nFast == nSlow)
         return true;
   }
   return false;
}

利用如下方法分别找到两个链表的环入口。首先设置一个快慢指针p_fast和p_slow,找到两个指针相交的点,p_inter。然后p从链表开头,p_slow从p_inter开始走,每次都走1步,则两个指针相交的地方,就是链表的入口。

(a) 分别求得A和B两个链表的入口,如果一样。则两个链表相交的第一个节点方法同1,只是将环当成NULL即可。

(b) 如果两个链表的环入口不一样,则没有第一个相交节点。

扩展2:

 如何找到入口点:

当fast若与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n)。假设slow走了s步,则fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则:

2s = s + nr
s= nr

设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)

(L – a – x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点,于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。程序描述如下:

Node findLoopPort(LinkedList lst){
   Node nFast = lst.head;
   Node nSlow = lst.head;

   while(nFast != null && nFast.next!= null){
      nFast = nFast.next.next;
      nSlow = nSlow.next;
      if(nFast == nSlow) break;
   }

   if(nFast == null || nSlow == null)
      return null;

   nSlow = head;
   while(nSlow != nFast){
      nSlow = nSlow.next;
      nFast = nFast.next;
   }

   return nSlow;
}



© 著作权归作者所有

关西大汉弹琵琶
粉丝 8
博文 41
码字总数 14221
作品 0
浦东
程序员
私信 提问
链表面试题(下)

一、题目 1、判断单链表是否带环?若带环,求环的长度?求环的入口点? ①链表是否带环问题。( 定义两个指针同时指向头节点,一个快指针,一个慢指针,两个指针同时遍历链表,快指针一次走两...

qq_38646470
2018/01/08
0
0
面试精选之链表问题集锦

链表问题是面试过程中经常被问到的一部分,很考查编程功底。最近刷了 LeetCode 上链表部分的面试题,我总结了一些有代表性的链表问题。 本文使用的是 Java 语言,下面是所用到的链表节点的定...

JohnnyShieh
2017/11/27
0
0
2018年5月23日滴滴新锐实习电话面试,开发岗位

1 自我介绍 2 java框架中spring框架的好处特点,ioc原理 3 项目介绍和sql优化做了什么,索引几种,数据结构,b+的特点,聚集索引的特点 4 进程间的通信方式 5 访问一个网页,详细的描述服务器...

牛客网
2018/05/24
0
0
142. Linked List Cycle II

题目描述:给一个链表,判断其中环的起始结点,若没有环则返回null。要求不改变链表,空间复杂度O(1)。 分析:这题与141题是同一个算法引出的一系列问题,即Floyd判圈算法,又称龟兔赛跑算法...

Nautilus1
2017/11/13
0
0
[算法总结] 一文搞懂面试链表题

本文首发于我的个人博客:尾尾部落 链表是面试过程中经常被问到的,这里把剑指offer 和 LeetCode 中的相关题目做一个汇总,方便复习。 1. 在 O(1) 时间删除链表节点 题目描述:给定单向链表的...

繁著
2018/08/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

前端技术之:Prisma Demo服务部署过程记录

安装前提条件: 1、已经安装了docker运行环境 2、以下命令执行记录发生在MackBook环境 3、已经安装了PostgreSQL(我使用的是11版本) 4、Node开发运行环境可以正常工作 首先需要通过Node包管...

popgis
今天
5
0
数组和链表

数组 链表 技巧一:掌握链表,想轻松写出正确的链表代码,需要理解指针获引用的含义: 对指针的理解,记住下面的这句话就可以了: 将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指...

code-ortaerc
今天
4
0
栈-链式(c/c++实现)

上次说“栈是在线性表演变而来的,线性表很自由,想往哪里插数据就往哪里插数据,想删哪数据就删哪数据...。但给线性表一些限制呢,就没那么自由了,把线性表的三边封起来就变成了栈,栈只能...

白客C
今天
40
0
Mybatis Plus service

/** * @author beth * @data 2019-10-20 23:34 */@RunWith(SpringRunner.class)@SpringBootTestpublic class ServiceTest { @Autowired private IUserInfoService iUserInfoS......

一个yuanbeth
今天
5
0
php7-internal 7 zval的操作

## 7.7 zval的操作 扩展中经常会用到各种类型的zval,PHP提供了很多宏用于不同类型zval的操作,尽管我们也可以自己操作zval,但这并不是一个好习惯,因为zval有很多其它用途的标识,如果自己...

冻结not
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部