内容简介:Given a linked list, return the node where the cycle begins. If there is no cycle, returnNote: Do not modify the linked list.Follow up:
Given a linked list, return the node where the cycle begins. If there is no cycle, return null
.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
快慢指针,参考 LeetCode - 141. Linked List Cycle
先判断是否有环,记录第一次相遇位置,然后快指针指向head指针,同步走,再次相遇时的节点即为环的入口。
证明:TODO
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null)
return null;
ListNode fast = head, slow = head;
int cnt = 0;
while (true) {
if (fast == null)
return null;
if (cnt > 0 && fast == slow)
break;
slow = slow.next;
fast = fast.next;
if (slow == null || fast == null)
return null;
fast = fast.next;
cnt ++;
}
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
数据挖掘导论
(美)Pang-Ning Tan、Michael Steinbach、Vipin Kumar / 机械工业出版社 / 2010-9 / 59.00元
本书全面介绍了数据挖掘的理论和方法,着重介绍如何用数据挖掘知识解决各种实际问题,涉及学科领域众多,适用面广。 书中涵盖5个主题:数据、分类、关联分析、聚类和异常检测。除异常检测外,每个主题都包含两章:前面一章讲述基本概念、代表性算法和评估技术,后面一章较深入地讨论高级概念和算法。目的是使读者在透彻地理解数据挖掘基础的同时,还能了解更多重要的高级主题。 本书特色 ·包含大量的图表、......一起来看看 《数据挖掘导论》 这本书的介绍吧!