很多网上的算法指根据结论倒推出a=c这样的结论,是错误的!
这道题比较注重数学推到,
如图,设置快慢两个指针,快指针的速度是慢指针的两倍
假设两个指针在z点相遇,那么快指针所走过的距离是慢指针的两倍
那么有以下公式,其中n代表快指针在环内转了n圈后行走b距离与慢指针相遇
2*(a+b)= a + b + n*(b+c) ====> a = (n-1)(b+c) + c
由这个推到结果可以知道,a的长度为n-1个环的长度加上c的长度
那么得出结论,相遇后,慢指针从链表头重新开始,快指针的速度和满指针一样继续前行,必然会在Y点相遇,相遇时快指针可能已经沿环转了多圈
package leetCode; /** * User: FR * Time: 10/28/14 1:35 PM * 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? */ public class LinkedListCycle2 { public ListNode detectCycle(ListNode head) { if(head == null){ return null; } ListNode slow = head; ListNode fast = head.next; while (fast != null){ if(slow == fast){ slow = head; fast = fast.next; while (slow != fast){ slow = slow.next; fast = fast.next; } return slow; } slow = slow.next; fast = fast.next; if(fast != null){ fast = fast.next; } } return null; } class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } public static void main(String[] args){ LinkedListCycle2 linkedListCycle = new LinkedListCycle2(); ListNode node1 = linkedListCycle.new ListNode(1); ListNode node2 = linkedListCycle.new ListNode(2); ListNode node3 = linkedListCycle.new ListNode(3); ListNode node4 = linkedListCycle.new ListNode(4); ListNode node5 = linkedListCycle.new ListNode(5); ListNode node6 = linkedListCycle.new ListNode(6); node1.next = node2; node2.next=node3; node3.next=node4; node4.next=node5; node5.next=node6; node6.next=node2; System.out.println(linkedListCycle.detectCycle(node1).val); } }
相关推荐
给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 null。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从
要考虑第一个节点要被删除的情况代码实现self.next = Nonedef removeElements(self, head: ListNode, val:
示例1输入: 1->1->2输出: 1->2示例2输入: 1->1->2->3->3输出: 1->2->3解题思路如果当前节点的值和下一个节点的值相等,则当前节
示例输入:输出: 1->1->2->3->4->4->5->6解题思路将k个链表建立成一个最小堆,再从堆顶pop()出每一个元素,连接成链表heapq是pyth
leetcode 链表-2 问题1 () 问题2 () 问题3 () 问题4 ()
leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 ...linked-list-cycle-ii 143 重排链表 reorder-list 148 排序链表 sort-list 234 回文链表 palindrome-linked-list 双指针遍历/滑动
leetcode 链表-1 问题1 () 问题2 () 问题3 ()
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....
1. 双指针迭代翻转链表 翻转链表和交换两个变量的操作大同小异。 首先需要一个prev指针(指着当前节点的前一个节点),一个cur指针(指着当前节点) 翻转链表需要注意的一点是:链表之间靠指针连接,如果贸然将某个...
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode伪代码convert-binary-number-in-a-linked-list-to-integer 题目解读: 题目来源: 原文: Given head which is a reference node to a singly-linked list. The value of each node in the linked list is ...
leetcode-链表笔记
答案leetcode-cn-java-algorithm-solution 我试图找到学习 leetcode 算法的最佳方法,所以我创建了它。 该项目将帮助您更好地学习 Leetcode 算法。 1. 入门 你想知道如何使用吗? 好的,现在让我们开始吧! 1.1 如何...
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
142-环形链表:linked-list-cycle-ii 160-相交链表:intersection-of-two-linked-lists 206-反转一个单链表:reverse-linked-list 20-有效的括号:valid-parentheses 150-逆波兰表达式求值:evaluate-reverse-polish-...
leetcode题库所有数据库问题 Leetcode 所有数据库问题:Leetcode 问题 Active-Businesses-LeetCode.png 活跃用户-LeetCode.png 活动-参与者-LeetCode.png 至少合作过三次的演员和导演-LeetCode.png Ads-Performance-...
解压Leetcode-Solution-With-Java 用 Java 8 解决 Leetcode 问题 编号 问题 解决方案 困难 01 简单的 02 中等的 03 无重复字符的最长子串 中等的 04 两个有序数组的中位数 难的 653 二和 IV - 输入是 BST 简单的 ...
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动态规划
leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站! ⦙⦙⦙⦙⦙⦙⦙⦙ 一个很打问题的方法。 问题来缓解离线思考。 编码前的源代码。 居住和与 leetcode.com。 下载你...
vs code LeetCode 插件