let 142. Linked List Cycle II

本文主要是介绍let 142. Linked List Cycle II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先如何找链表有环
解法：
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null) return false;
ListNode first=head;
ListNode second=head;
while(second.next!=null&&second.next.next!=null){

        first=first.next;second=second.next.next;if(first==second) return true;}return false;
}

}

现在提升，难度，找到环开始的地方，根据如下规则，
假设环开始的i地方是头接点走A 步， 当发现环时 第一个慢节点总共走了A+B步，那么快节点走了2A+2B步， 快节点比慢节点夺走了一个环的长度，环的长度为N
N=A+B
当头接点走A步的时候，慢节点再走A步， A+B+B=N+A，慢节点就是走A+一个环的距离，此时慢节点和头接点正好相等。所以可以确认环开始的位置。AC 代码如下：public class Solution {public ListNode detectCycle(ListNode head) {if(head==null) return null;if(head.next==head) return head;ListNode first=head;ListNode second=head;while(second.next!=null&&second.next.next!=null){first=first.next;second=second.next.next;if(first==second){ListNode start=head;while(start!=first){start=start.next;first=first.next;}return start;}}return null;}
}

这篇关于let 142. Linked List Cycle II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---