链表环操作（java实现）

1. 判断链表有没有环
   

   有环链表
   一般我们采取快慢指针来判断链表是否有环。思路主要是：

   定义两个指针。fast和slow；
   fast和slow都从head开始往后走。顾名思义，fast走得快一点，每次走两步；slow走得慢一点，每次走一步；
   没有环的情况下，fast肯定率先走到尾结点；
   有环的情况下，fast先入环，slow后入环。因为fast比slow每次都多走一步，所以最终在某个地方会相遇（就像跑800m的时候，A跑得特别快，B跑得特别慢；A最后在某个地方又追上了B，超了B一圈）。

   看懂了上面的分析，应该就能写出相应的代码。

   public class 判断链表是否有环 {
       public boolean isLoop(ListNode head){
           ListNode slow = head;
           ListNode fast = head;
           while(fast.next != null && fast.next.next != null){
               slow = slow.next;
               fast = fast.next.next;
               if(slow == fast){
                   return true;
               }
           }
           return false;
       }
   }
   

2. 有环的话找到入口结点

   
   入口结点.png

   我们要求的是D（入口结点），现在已知的是I（相遇点，按照第一题的快慢指针可以求得）。这道题目有点像数学题，我们来推导一下：

   slow走x步的时候，fast走了2x步，其中在环内走了x步；
   然后我们要知道，第一次相遇的时候slow还未走完一圈（最多走完一圈），同样我们想象两个人跑800m，A速度是2m/s,B是1m/s。A跑完2圈，B跑完1圈的时候两个人相遇。这是最极端的情况，即两个人是从同一个起点开始跑的。而在本题内，一般情况下，fast都会比slow先多走几步，这样fast追上slow所用的时间又会少一点；
   那么相遇的时候，slow在环内走了s步，fast在环内走了x+2s步；
   假设fast已经走了n圈。那么有下面的等式：
   s=x+2s-nc，即s=nl-x=(n-1)c+c-x;
   我们可以把(n-1)c+c-x理解为，fast先走完(n-1)圈，再走了c-x步。
   由此我们可以知道，在相遇点的时候，我们再走x步就能又回到入口结点。那么I到D的距离就是x，和A到D的距离是一样的

   然后是代码：

   public class 环的入口结点 {
   
       public ListNode EntryNodeOfLoop(ListNode pHead) {
           ListNode slow = pHead;
           ListNode fast = pHead;
           while(fast.next != null && fast.next.next != null){
               slow = slow.next;
               fast = fast.next.next;
               if(slow == fast){ // 相遇就跳出循环
                   break;
               }
           }
           if(fast.next == null || fast.next.next == null){
               return null;
           }
           ListNode p1 = pHead; // 头结点
           ListNode p2 = slow; // 相遇结点
           while(p1 != p2){ // 相等的时候即p1、p2同时到达相遇结点
               p1 = p1.next;
               p2 = p2.next;
           }
           return p1;
       }
   }
   

3. 环结点个数
   这个问题在我们会求相遇点后已经变得非常简单。我们让slow继续走走走，又走回到相遇点就代表走完了一圈，就能求得环长

   public class 环结点个数 {
       public static int nodeNumOfLoop(ListNode head){
           ListNode fast = head;
           ListNode slow = head;
           int count = 0; // count计数
           while(fast.next != null && fast.next.next != null){
               slow = slow.next;
               fast = fast.next.next;
               if(slow == fast){
                   break;
               }
           }
           if(fast.next == null || fast.next.next == null){
               return 0;
           }
           ListNode temp = slow;
           do{
               slow = slow.next;
               count++;
           } while(slow != temp);
           return count;
       }
   }
   

4. 链表长度
   看第2题的图，总长就=c+x嘛！

   public class 链表长度 {
   public static int lLength(ListNode head){
       ListNode p1 = head;
       int length = 0;
       if(meetNode(head) == null){
           while(p1 != null){
               p1 = p1.next;
               length++;
           }
           return length;
       }else{
           return EntryNodeOfLoop(head)+nodeNumOfLoop(head);
       }
   
   }
   public static ListNode meetNode(ListNode head){  // 相遇点
       ListNode slow = head;
       ListNode fast = head;
       while(fast.next != null && fast.next.next != null){
           slow = slow.next;
           fast = fast.next.next;
           if(slow == fast){
               return slow;
           }
       }
       return null;
   }
   public static int EntryNodeOfLoop(ListNode head){ // 环入口结点距头结点的距离
       int count = 0;
       ListNode p1 = head;
       ListNode p2 = meetNode(head);
       while(p1 != p2){
           p1 = p1.next;
           p2 = p2.next;
           count++;
       }
       return count;
   }
   public static int nodeNumOfLoop(ListNode head){ // 环长度（环结点个数）
       int count = 0;
       ListNode slow = meetNode(head);
       ListNode temp = slow;
       do{
           slow = slow.next;
           count++;
       } while(slow != temp);
       return count;
   }
   }
   

总结一下。

第一个，判断是否有环。转换成求相遇结点的问题，用快慢指针解决。相遇则有环，反之无环。
第二个，求入口结点（D）。先求相遇结点，然后记住一个结论。头结点到入口结点的距离（x)与相遇结点到入口结点的距离相同。
第三个，求环结点个数（c）。求相遇结点，然后走一圈，计数。
第四个，求链表长度。转换成求相遇结点+求入口结点的问题。然后x（根据入口结点求得）+c（根据相遇结点求得）

不管三七二十一，相遇结点总是要求的，从一开始拿到问题，就要判断成不成环，反正要求的！就连入口结点也是根据相遇结点求的。然后其他问题就是求相遇结点和入口结点的变体了。