题目要求:给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路一: Floyd环判定算法

使用fastptr和sloeptr两个速度不相同的指针,一旦它们两个进入链表中的环,就肯定会相遇

时间复杂度O(n)

空间复杂度O(1)

错误代码:没有看清楚题目啊?不是让你判断链表是否有环,而是要让你找到环的入口节点啊

 

 1 public class Solution {
 2     public ListNode EntryNodeOfLoop(ListNode pHead){
 3         //考虑特殊情况
 4         if(pHead == null || pHead.next==null|| pHead.next.next==null) return null;
 5         //定义两个pointer
 6         ListNode fastptr = pHead;//快指针走两步
 7         ListNode slowptr = pHead;//慢指针走一步
 8         while( fastptr.next.next!=null && slowptr.next!=null){
 9             fastptr = fastptr.next.next;
10             slowptr = slowptr.next;
11             if(fastptr == slowptr) return fastptr;
12         }
13         return null;
14     }
15 }

 

正确代码: 

25行的break语句,一定要放进if的{}中去,否则无法通过

 1 /*
 2  public class ListNode {
 3     int val;
 4     ListNode next = null;
 5 
 6     ListNode(int val) {
 7         this.val = val;
 8     }
 9 }
10 */
11 public class Solution {
12     public ListNode EntryNodeOfLoop(ListNode pHead){
13         //考虑特殊情况
14         if(pHead == null || pHead.next==null|| pHead.next.next==null) return null;
15         //定义两个pointer,和环是否存在的真假
16         ListNode fastptr = pHead;//快指针走两步
17         ListNode slowptr = pHead;//慢指针走一步
18         boolean isExist = false;
19         //判断环是否存在
20         while( fastptr.next.next!=null && slowptr.next!=null){
21             fastptr = fastptr.next.next;
22             slowptr = slowptr.next;
23             if(fastptr == slowptr){
24                 isExist = true;
25                 break;
26             }
27         }
28         if(isExist == true){//环存在,找到环的入口节点
29             slowptr = pHead; //只初始化其中一个指针,另外一个指针不动
30             while(slowptr!= fastptr){
31                 fastptr = fastptr.next; //每个指针各走一步
32                 slowptr = slowptr.next; //每个指针各走一步
33             }
34             return slowptr;
35         }
36         return null; //环不存在,返回null
37     }
38 }