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?
算法参见Wekipedia.
1. 假设圈的周长λ,相遇的时候乌龟走的路程:μ + k, 而兔子走的路程:μ + k + n*λ,(n代表兔子走了多少圈)
2. 因为兔子的速度是乌龟的两倍,所以兔子走的路程是乌龟的两倍,2(μ + k) = μ + k + n*λ,得到μ = n*λ - k = (n-1)λ + (λ-k)
3. 从相遇点的时候开始,乌龟从开始点走起,兔子从相遇点继续走,而且这时两者走的速度是一样的,那么当乌龟从头走到循环点X的时候,走了μ路程,而兔子走的路程是n*λ - k,两者的路程是一样的,相遇点必然是X。
public ListNode detectCycle(ListNode head) { ListNode walker = head, runner = head; do { if(runner == null || runner.next == null) { return null; } walker = walker.next; runner = runner.next.next; } while(walker != runner); walker = head; while(walker != runner) { walker = walker.next; runner = runner.next; } return walker; }
相关推荐
leetcode中文版 LeetCode/Cpp 本人刷题记录在此,包含题意理解与算法思路,包含在Cpp文件内部...142.Linked List Cycle II(solve1) LeetCode 142.Linked List Cycle II(solve2) LeetCode 160.Intersection of Two Linke
leetcode 答案leetcode-java leetcode.com 的 Java 答案 ================索引================ com.leetcode.array Search a 2D Matrix Spiral Matrix com.leetcode.list Linked List Cycle Linked List Cycle II ...
leetcode 不会 Leetcode Solutions in Java Linked List Linked List Cycle Given a linked list, determine if it has a cycle in it. public static boolean hasCycle(ListNode head) 快慢指针法,块指针从head....
142-环形链表:linked-list-cycle-ii 160-相交链表:intersection-of-two-linked-lists 206-反转一个单链表:reverse-linked-list 20-有效的括号:valid-parentheses 150-逆波兰表达式求值:evaluate-reverse-polish-...
leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 ...linked-list-cycle-ii 143 重排链表 reorder-list 148 排序链表 sort-list 234 回文链表 palindrome-linked-list 双指针遍历/滑动
leetcode怎么销号 LeetCode便签 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? 解决思路 声明一个慢指针和一个快...
java lru leetcode leetcode-java leetcode刷题笔记 已做题目列表 ...142.Linked List Cycle II 188.Best Time to Buy and Sell Stock IV 217.Contains Duplicate 263.Ugly Number 264.Ugly Number II
linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to...
leetcode卡 leetcode exercises 3-5 solutions everyday. fighting~ TODO array Best Time to Buy and Sell Stock II Valid Sudoku linked list Palindrome linked list Linked List Cycle trees Convert Sorted ...
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
leetcode中国 Leetcode Set Matrix Zeroes 第一种 通过一次遍历记录所有为0的索引(Python中enumerate()输出当前列表的索引) 再遍历一次, 根据记录的索引进行置0 第二种 通过一次遍历所有为0的索引, 设置当前索引的...
preorder-traversal链表reorder-list链表linked-list-cycle-ii链表linked-list-cycle动态规划word-break-ii动态规划word-break链表copy-list-with-random-pointer复杂度single-number-ii复杂度single-number动态规划
141.Linked-List-Cycle │ ├── solution.cpp │ ├── solution.go │ └── solution.md [ -> Explain thoughts about this problem.] ├── 404.Sum-of-Left-Leaves │ ├── solution.cpp │ ├...
leetcode 答案Leet Code 挑战 这是我提交给 Lambda School CS Unit 2 构建周的已接受 ...如果您想自己尝试,这些链接将带您进入代码挑战。...要查看我接受的答案,只需转到与代码挑战名称匹配的...II](https://leetcode.co
leetcode 答案 LeetCodeSolution This is the solutions set of the LeetCode Website's problems. Some Information Language :Java Website url : Why to Do : Everyday Code is interesting Notes Climbing ...
linked-list-cycle/Solution.993783.java $ tree . ├── add-binary │ └── Solution.665166.java ├── add-two-numbers │ └── Solution.666385.java ├── balanced-binary-tree │ └── ...
leetcode 2 sum c LeetCode 帮助文档 帮助文档存放在Help文件夹下。 文件名 文件描述 链接 complexitypython.txt Python的一些常规操作的复杂度统计 题目清单 Array(数组) ID Difficulty Title Java Python 1 Easy ...
leetcode添加元素使和等于 总结 按照类别分类来刷 刷当前题的时候,看下『题目描述』最底下有个『相似题目』,这些题的思路...linked-list-cycle-ii reverse-nodes-in-k-group 二叉树 实现一个二叉树 二叉树二叉树的
II(Linked List Cycle II) 2018.9.26 删除排序链表中的重复元素 II(Remove Duplicates from Sorted List II) 2018.9.27 重建二叉树(Rebuild Binary Tree) 2018.9.28 把字符串转换成整数(Convert a string to ...
leetcode 2 sum c LeetCode 贵有恒,何必三更起五更睡;最无益,只怕一日暴十寒。 我的个人网站: 分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类文章,欢迎您的关注! 帮助文档 帮助文档...