LeetCode解题报告:Linked List Cycle && Linked List Cycle II

1题目

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:

Can you solve it without using extra space?

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:

Can you solve it without using extra space?

2思路

2.1 对于判断链表是否有环

用两个指针,一开始都指向头结点,一个是快指针,一次走两步,一个是慢指针,一次只走一步,当两个指针重合时表示存在环了。

证明:假设链表有环,环的长度为N,慢指针在起始位置,快指针在位置k(位置从0开始计数),那么快指针只要比慢指针多走经过N-k步,就可以追上慢指针了。,因为每一次快指针都比慢指针多走一步,所以一定可以在有限的步数追上慢指针。

2.2如何求出环的起始位置

结论:当快指针和慢指针重合的时候,把一个指针重新指向头指针,两个指针现在速度一样,一次走一步,那么当两个指针值相同时,所在的指针就是环的起始位置。



证明:假设头指针到环的其实位置的长度是k,环的长度是loop,两个指针相遇的时候,慢指针距离还的起始位置的长度是m。

计算:因为快指针的速度是慢指针的两倍。可以推断出:

distance(快指针) = 2 * distance(慢指针),即

k + loop + m = 2 * ( k + m ) ,化解得出

loop = k + m

分析起始点的位置:通过慢指针继续走loop - m步就可以到达环的起始位置,正好k=loop - m,所以,相遇时把快指针指向头指针,两个指针以相同的速度走k步就可以一起到达环的起始位置了。

可以看看这篇文章的解释,看着像我邮学长的blog

3 代码

public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
boolean hasCycle = false;
while (fast != null && (fast.next != null)) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
hasCycle = true;
break;
}
} // find the start of cycle
if (!hasCycle) {
return null;
}
for (fast = head; fast != slow;) {
fast = fast.next;
slow = slow.next;
}
return fast;
}

最新文章

  1. Java学习笔记(05)
  2. ComponentOne 2016 V3 发布
  3. JSON.stringify() / JSON.parse()
  4. motto2
  5. 微软WTL模板库完整版安装(VS2010+windows7X64位环境下)分享
  6. 多进程和atexit清理函数
  7. JAVA 网格布局管理器
  8. Android 一步步教你从ActionBar迁移到ToolBar
  9. mkdir、whoami、touch
  10. 重构后的程序:通过rsync命令抓取日志文件
  11. oracle数据泵之解决方案(用户)导入导出。
  12. JavaScript之数组学习
  13. TCP与UDP在socket编程中的区别 (网络收集转载)
  14. Jenkins中集成Gcov代码覆盖率报告
  15. Storm源码分析--Nimbus-data
  16. javascript 表达式和运算符 (二)
  17. 使用一个for循环将N*N的二维数组的所有值置1
  18. Guangcong Wang王广聪的主页
  19. Matlab中的rectangle函数
  20. Redis 学习之路 (011) - redis 多数据库

热门文章

  1. JavaScript 应用开发 #5:为完成的任务添加样式
  2. Eclipse优化集合,Eclipse优化速度,解决Ctrl+C、Ctrl+V卡
  3. build/envsetup.sh内lunch解析
  4. C#入门教程(二)–C#常用快捷键、变量、类型转换-打造C#学习教程
  5. 两种隐藏元素方式【display: none】和【visibility: hidden】的区别及由此引出的问题
  6. struts启动报错Javassist library is missing
  7. java csv - 读写及其操作.
  8. SQL Prompt Snippet Manager 妙用
  9. VS2008 未找到编译器可执行文件 csc.exe【当网上其他方法试玩了之后不起作用的时候再用这个方法】
  10. UITabBar的隐藏