本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!