分析

难度 中

来源

环之前节点数 a；从环起始节点到快慢指针相遇位置，节点数 b

快慢指针fast slow相遇，慢指针走过 a+b，快指针走过2*(a+b)

快慢指针相遇时，创建第二个慢指针 slow2

同上，slow再走过a+b时，slow走过2(a+b)，slow2走过a+b，

二者在快慢指针相遇处相遇。slow slow2速度相同，

往前回推，二者从环开始处即相遇然后并行                       

题目

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?

解答

1 package LeetCode; 2  3 public class L142_LinkedListCycleII { 4     public ListNode buildList(int[] nums,boolean withCircle){ 5         int len=nums.length; 6         ListNode head; 7         ListNode pointer; 8         pointer=head=new ListNode(nums[0]); 9         for(int i=1;i
        
         0.5)46             ln=l142.buildList(nums,true);47         else48             ln=l142.buildList(nums,false);49         ListNode result=l142.detectCycle(ln);50         if(result!=null)51             System.out.println(result.val);52         else53             System.out.println("没有环");54     }55 }