剑指offer_23_链表中环的入口节点

// 链表中环的节点入口
public static ListNode findNode(ListNode node) {
    if (node == null ) {
        return null;
    }
    // 找到在环中相遇的节点
    ListNode mettingNode = findMettingNode(node);
    // 求取环的大小
    int count = findCount(mettingNode);
    // 求出环的开始节点
    return findStartNode(node, count);
}

// 找到指针在链表相遇的节点
public static ListNode findMettingNode(ListNode node) {
    ListNode fast = node;
    ListNode slow = node;
    if (node.next == null) {
        return null;
    }
    while ((fast = fast.next) != null && (slow=slow.next.next) != null ) {
        if (fast == slow) {
            return fast;
        }
    }
    return null;
}

// 求取链表中环的大小
public static int findCount(ListNode node) {
    // 定义俩个"指针"
    if (node == null) {
        return 0;
    }
    ListNode move = node;
    int count = 0;
    while ((move = move.next) != null) {
        count++;
        if (move == node) {
            return count;
        }
    }
    return 0;
}
// 求环所在的节点
public static ListNode findStartNode(ListNode node,int count) {
    if (count == 0) {
        return null;
    }
    ListNode nodeFirst = node;
    ListNode nodeLast = node;

    while (count != 0) {
        count--;
        nodeFirst = nodeFirst.next;
    }
   while (nodeFirst != nodeLast) {
        nodeFirst = nodeFirst.next;
        nodeLast = nodeLast.next;
   }
   return nodeFirst;
}