android开发环境,谷歌优化 网站建设,wordpress加密c酱酱,商业网站的域名代码转载自 玻璃猫 程序员小灰
大四毕业前夕#xff0c;计算机学院#xff0c;
正在四处求职的小灰碰到了同系的学霸大黄…… 小灰边说边回忆着上周去面试的情形…… 有一个单向链表#xff0c;链表当中有可能出现“环”#xff0c;就像下图这样。如何用程序判断出这个链表是…转载自 玻璃猫 程序员小灰
大四毕业前夕计算机学院
正在四处求职的小灰碰到了同系的学霸大黄…… 小灰边说边回忆着上周去面试的情形…… 有一个单向链表链表当中有可能出现“环”就像下图这样。如何用程序判断出这个链表是有环链表 方法一首先从头节点开始依次遍历单链表的每一个节点。每遍历到一个新节点就从头节点重新遍历新节点之前的所有节点用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID则说明该节点被遍历过两次链表有环如果之前的所有节点当中不存在相同的节点就继续遍历下一个新节点继续重复刚才的操作。
例如这样的链表A-B-C-D-B-C-D 当遍历到节点D的时候我们需要比较的是之前的节点A、B、C不存在相同节点。这时候要遍历的下一个新节点是BB之前的节点A、B、C、D中恰好也存在B因此B出现了两次判断出链表有环。
假设从链表头节点到入环点的距离是D链表的环长是S。那么算法的时间复杂度是0123….(DS-1) (DS-1)*(DS)/2 可以简单地理解成 O(N*N)。而此算法没有创建额外存储空间空间复杂度可以简单地理解成为O(1)。 方法二首先创建一个以节点ID为键的HashSet集合用来存储曾经遍历过的节点。然后同样是从头节点开始依次遍历单链表的每一个节点。每遍历到一个新节点就用新节点和HashSet集合当中存储的节点作比较如果发现HashSet当中存在相同节点ID则说明链表有环如果HashSet当中不存在相同的节点ID就把这个新节点ID存入HashSet之后进入下一节点继续重复刚才的操作。
这个方法在流程上和方法一类似本质的区别是使用了HashSet作为额外的缓存。
假设从链表头节点到入环点的距离是D链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1), 所以总体的时间复杂度是1*(DS)DS可以简单理解为O(N)。而算法的空间复杂度还是DS-1可以简单地理解成O(N)。 等通知就是没通知这是职场上公认的语言。
以上就是小灰悲剧的回忆…… 方法三首先创建两个指针1和2在java里就是两个对象引用同时指向这个链表的头节点。然后开始一个大循环在循环体中让指针1每次向下移动一个节点让指针2每次向下移动两个节点然后比较两个指针指向的节点是否相同。如果相同则判断出链表有环如果不同则继续下一次循环。
例如链表A-B-C-D-B-C-D两个指针最初都指向节点A进入第一轮循环指针1移动到了节点B指针2移动到了C。第二轮循环指针1移动到了节点C指针2移动到了节点B。第三轮循环指针1移动到了节点D指针2移动到了节点D此时两指针指向同一节点判断出链表有环。
此方法也可以用一个更生动的例子来形容在一个环形跑道上两个运动员在同一地点起跑一个运动员速度快一个运动员速度慢。当两人跑了一段时间速度快的运动员必然会从速度慢的运动员身后再次追上并超过原因很简单因为跑道是环形的。 假设从链表头节点到入环点的距离是D链表的环长是S。那么循环会进行S*K次K为正整数为什么是S*K次有心的同学可以自己揣摩下可以简单理解为ON。除了两个指针以外没有使用任何额外存储空间所以空间复杂度是O1。 问题一判断两个单向链表是否相交如果相交求出交点。 问题二在一个有环链表中如何找出链表的入环点
