LinkedList

• 环形链表I
  
  一个简单的想法是使用快慢指针，快指针一次走两步，慢指针一次走一步，当快指针指向null时，慢指针指向的节点
  这个想法可以类比于龟兔赛跑,由于兔子及快导致如果有环,会一直再环里转圈,总会到一个位置相遇

  public class Solution {
      public boolean hasCycle(ListNode head) {
          if(head==null||head.next==null){
              return false;
          }
          ListNode low = head;
          ListNode fast = head.next;
          while(fast!=low){
              if(fast==null||fast.next==null){      // 注意判空条件
                  return false;
              }
              low=low.next;
              fast=fast.next.next;
          }
          return true;
      }
  }

• 环形链表II
  
  在第一题的基础上加入了求环形链表的入口点
  与上一题相同,设立快慢指针,假设慢指针到入口的距离是a,到快指针的相遇点是a+b
  假设环的跨度是c
  那么我们可以进行得到的是fast = a+b+nc
  
  slow = a+b
  
  且fast = 2slow
  
  所以有a+b+nc = 2(a+b)
  
  所以有a+b = nc
  
  当我们假设b只有一圈的时候, a = nc - b
  
  这时候我们可以得到的结论是, 当我们重新设立一个新的指针, 指向head, 然后两个指针(slow与nPtr)同时移动
  那么我们可以进行得到的是a,也即入口指针

  public class Solution {
      public ListNode detectCycle(ListNode head) {
          ListNode slow = head;
          ListNode fast = head;
          while(true){   //值得注意的是本处的快慢指针不能使用不同起点,具体原因想不通
              if(fast == null|| fast.next ==null) return null;
              fast=fast.next.next;
              slow=slow.next;
              if(fast==slow) break;
          }
          fast = head;
          while(fast != slow){
              fast = fast.next;
              slow = slow.next;
          }
          return fast;
      }
  }