首页 > 代码库 > JAVA-Linked List Cycle I&&Linked List Cycle II
JAVA-Linked List Cycle I&&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?
第一题要求是否有环 从图中可以看出 使用快慢指针 只要有环两者必定会相遇 另外从相遇点可以看出 相遇点距离环的起始点的距离与head到起始点的距离是相同的 只要再设一指针 与slow一起走 相遇点即环的起始点
若设 环的大小为 a 快慢指针的路程分别为x和y 则 x+a=y ， y=2x ==>x=a;即慢指针走过的路程恰为环的大小 此时从相遇点到环起点恰为整个链表的长度 而从head出发恰好差一个环的距离 所以相遇点必为环的起点 代码如下：
public class Solution { public ListNode detectCycle(ListNode head) { if(head==null||head.next==null) return null; ListNode slow=head; ListNode fast=head; int count=0; while(fast.next!=null&&fast.next.next!=null){ slow=slow.next; fast=fast.next.next; count++; if(slow==fast) break; } if(slow==fast&&count!=0){ ListNode res=head; while(res!=slow){ res=res.next; slow=slow.next; } return res; }else{ return null; } }}JAVA-Linked List Cycle I&&Linked List Cycle II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。