- 浏览: 173912 次
- 性别:
- 来自: 济南
文章分类
最新评论
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?
判断一个链表中是否有环存在,并且输出环的起始点。我们用快慢指针fast,slow来判断是否有环存在,如果它们可以相遇就说明有环存在,如果不能相遇说明没有环存在。它们相遇之后,图中的meet点是它们的相遇点,假设join为环的起始点,我们假设head到join的距离为a, join到meet的距离为b(逆时针),meet到join的距离为c(逆时针)。如果它们相遇,那么fast走过的路程是slow走过的两倍,所以a + b + c + b = 2 ( a + b),即a = c。有了这个关系我们只需要用两个指针一个从相遇点出发,另一个从头结点出发,它们相遇的点就是环的起始点。代码如下:
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
判断一个链表中是否有环存在,并且输出环的起始点。我们用快慢指针fast,slow来判断是否有环存在,如果它们可以相遇就说明有环存在,如果不能相遇说明没有环存在。它们相遇之后,图中的meet点是它们的相遇点,假设join为环的起始点,我们假设head到join的距离为a, join到meet的距离为b(逆时针),meet到join的距离为c(逆时针)。如果它们相遇,那么fast走过的路程是slow走过的两倍,所以a + b + c + b = 2 ( a + b),即a = c。有了这个关系我们只需要用两个指针一个从相遇点出发,另一个从头结点出发,它们相遇的点就是环的起始点。代码如下:
/** * 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 || head.next == null) return null; ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if(slow == fast) break; } if(fast != slow) return null; fast = head; while(fast != slow) { fast = fast.next; slow = slow.next; } return fast; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 227Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 229You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 343Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 335Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 452Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 514Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 431Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 622Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 429The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 388Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 520Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 534Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 371All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 862Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 883Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 557Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 602Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 766Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 737You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 631For a undirected graph with tre ...
相关推荐
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 ...
List LeetCode 92.Reverse Linked List II LeetCode 138.Copy List with Random Pointer LeetCode 142.Linked List Cycle II(solve1) LeetCode 142.Linked List Cycle II(solve2) LeetCode 160.Intersection of Two ...
java lru leetcode leetcode-java leetcode刷题笔记 已做题目列表 1.Two Sum 3.Longest Substring Without Repeating Characters 5.Longest ...II ...141.Linked List Cycle 142.Linked List Cycle II ...II
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]...
II 快慢指针再加个初始指针 慢指针到链表开始位置时, 快指针总是比他快k步(每次移动快1步, 移动k次), 第一次相遇的时候快慢指针位置距离链表起始位置差k步即在n-k的位置(链表环长度为n) Majority Element 多数投票...
leetcode 答案Leet Code 挑战 这是我提交给 Lambda School CS Unit 2 构建周的已接受 ...如果您想自己尝试,这些链接将带您进入代码挑战。...要查看我接受的答案,只需转到与...[Linked List Cycle II](https://leetcode.co
leetcode 答案leetcode-java ...的 Java ...II Remove Duplicates from Sorted List com.leetcode.string Single Number com.leetcode.tree Balanced Binary Tree Maximum Depth of Binary Tree Same Tree
Linked List Linked List Cycle Given a linked list, determine if it has a cycle in it. public static boolean hasCycle(ListNode head) 快慢指针法,块指针从head.next开始,慢指针从head开始,快指针每次移动...
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
java二叉树算法源码 algorithm-primer algorithm primer - 算法基础、Leetcode编程、剑指offer 目录 Leetcode编程 Leetcode Category 栈与队列 ...List ...Linked List Cycle ...环形链表II Linked List Cycle I
leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 ...linked-list-cycle-ii 143 重排链表 reorder-list 148 排序链表 sort-list 234 回文链表 palindrome-linked-list 双指针遍历/滑动
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 ...
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动态规划
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 问题描述 Given a linked list, determine if it has a cycle in it. Follow up:Can you solve it without using extra space? 解决思路 声明一个慢指针和一个快指针 慢指针一次后移一个节点,快...
leetcode 2 sum c LeetCode 贵有恒,何必三更起五更睡;最无益,只怕一日暴十寒。 我的个人网站: 分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类...Cycle 160 * Intersection of Two Linke
leetcode 2 sum c LeetCode 贵有恒,何必三更起五更睡;最无益,只怕一日暴十寒。 我的个人网站: 分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类...Cycle 160 * Intersection of Two Linke