剑指offer_链表---链表中环的入口结点

/**
 * 
 */
package 链表;
/**
 * <p>
 * Title:EntryNodeOfLoop
 * </p>
 * <p>
 * Description:
 * </p>
 * 
 * @author 田茂林
 * @data 2017年8月23日 上午9:25:08
 */
public class EntryNodeOfLoop {
  public ListNode NodeEntryNodeOfLoop(ListNode pHead) {
    if (pHead == null) {
      return null;
    }
    // 先找到碰撞点，两个指针出发，一快一慢
    ListNode fast = pHead;
    ListNode slow = pHead;
    if (fast == null || fast.next == null) {
      return null;     //因为下边的循环要用到fast.next，所以不能为null
    }
    while (fast != null) {   //因为函数体里没有用到fast.next做判断，只有赋值操作，所以不需要对其做非空判断。
      fast = fast.next.next;
      slow = slow.next;//slow的速度比fast慢，所以不用判断slow是否非空
      if (fast == slow)
        break;
    }
    // 速度一样的两个指针一个从pHead出发，一个从碰撞点出发，相遇的地方就是入口节点
    slow = pHead;
    while (slow != fast) {
      slow = slow.next;
      fast = fast.next;
    }
    return slow;
  }
}