新博文地址:[leetcode]Linked List Cycle II
http://oj.leetcode.com/problems/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?
Follow up:
Can you solve it without using extra space?
判断一个链表是否含有环,如包含,则返回环的起点。
这道题,有一种很高大上的解法,算法思想具体步骤有两步:(如何检测就不多说了)
1. Once a loop as been detected (step-3 above), move one of the pointers to the beginning (head) of the linked list. The second pointer remains where it was at the end of step-3.
2. Increment both pointers one node at a time. The node at which the two pointers meet will be the starting node of the loop!
2. Increment both pointers one node at a time. The node at which the two pointers meet will be the starting node of the loop!
具体就是,
1.找到第一次相遇到的节点(http://huntfor.iteye.com/admin/blogs/2052045),快指针就指向该节点,慢指针重新指向头结点;
2. 然后这两个指针均每次走一步,则第二次相遇的节点即为头结点
具体的算法分析请移步
http://umairsaeed.com/2011/06/23/finding-the-start-of-a-loop-in-a-circular-linked-list/
代码实现起来也是非常简单的:
public ListNode detectCycle(ListNode head) { ListNode meetNode = hasLoop(head);//判断是否有环,如有,则返回第一次相遇节点 if(meetNode == null){ return null; } ListNode slow = head; ListNode fast = meetNode; while(fast != slow){ slow = slow.next; fast = fast.next; } return fast; }
相关推荐
leetcode中文版 LeetCode/Cpp 本人刷题记录在此,包含题意理解与算法思路,包含在Cpp文件内部注释,后续会持续更新。 有不懂的可以联系ji648513181,同时也欢迎志同道合O的朋友一起合作更新。 已更新剑指Offer答案...
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 ...
* [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-java leetcode.com ...II Remove Duplicates from Sorted List com.leetcode.string Single Number com.leetcode.tree Balanced Binary Tree Maximum Depth of Binary Tree Same Tree
leetcode leetcode-java leetcode刷题笔记 已做题目列表 1.Two Sum 3.Longest Substring Without Repeating Characters 5.Longest Palindromic Substring 20.Valid Parentheses 26.Remove Duplicates from Sorted ...
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....
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? 解决思路 声明一个慢指针和一个快...
leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 ...linked-list-cycle-ii 143 重排链表 reorder-list 148 排序链表 sort-list 234 回文链表 palindrome-linked-list 双指针遍历/滑动
leetcode 2 sum c LeetCode 帮助文档 ...Cycle 160 Easy Intersection of Two Linked Lists 203 Easy Remove Linked List Elements no 206 Easy Reverse Linked List 234 Easy Palindrome Linked List
II 快慢指针再加个初始指针 慢指针到链表开始位置时, 快指针总是比他快k步(每次移动快1步, 移动k次), 第一次相遇的时候快慢指针位置距离链表起始位置差k步即在n-k的位置(链表环长度为n) Majority Element 多数投票...
java二叉树算法源码 algorithm-primer algorithm primer - 算法基础、Leetcode编程、剑指offer 目录 Leetcode编程 Leetcode Category 栈与队列 ...List ...Linked List Cycle ...环形链表II Linked List Cycle I
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动态规划
II Valid Sudoku linked list Palindrome linked list Linked List Cycle trees Convert Sorted Array to Binary Search Tree string and search First Bad Version Dynamic Programing *** Climbing Stairs Set ...
142-环形链表:linked-list-cycle-ii 160-相交链表:intersection-of-two-linked-lists 206-反转一个单链表:reverse-linked-list 20-有效的括号:valid-parentheses 150-逆波兰表达式求值:evaluate-reverse-polish-...
终生成长 :hot_beverage: 为什么要建这个仓库 梳理自己掌握的知识点,整理自己的知识体系。 I Hear and I Forget, I See and I ... Linked List CycleLeetcode 21. Merge Two Sorted ListsLeetCode 224. Basic Cal
linked-list-cycle/Solution.993783.java $ tree . ├── add-binary │ └── Solution.665166.java ├── add-two-numbers │ └── Solution.666385.java ├── balanced-binary-tree │ └── ...
linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to...
Linked List Cycle II Reorder List LRU Cache Palindrome Linked List 字符串 Valid Palindrome Implement strStr() String to Integer (atoi) Add Binary Longest Palindromic Substring Regular Expression ...
leetcode 2 sum c LeetCode 贵有恒,何必三更起五更睡;最无益,只怕一日暴十寒。 我的个人网站: 分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类...Cycle 160 * Intersection of Two Linke
leetcode 答案Leet Code 挑战 这是我提交给 Lambda School CS Unit 2 构建周的已接受 ...如果您想自己尝试,这些链接将带您进入代码挑战。...要查看我接受的答案,只需转到与代码挑战名称匹配的...II](https://leetcode.co