链表中环的入口节点

《剑指offer》面试题23：链表中环的入口节点

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

思路：
　　原书中给出的思路：解决问题的第一步是如何确定一个链表有环。我们可以用两个指针来解决这个问题。定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走的快的指针追上了走得慢的指针，那么链表就包含环；如果走的快的指针走到了链表的末尾都没有追上第一个指针，那么链表就不包含环。
　　第二步是如何找到环的入口。我们还是用两个指针来解决这个问题。先定义两个指针p1和p2指向链表的头节点。如果链表的环中有n个节点，则指针p1先在链表上向前移动n步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口节点时，第一个指针已经围绕着环走了一圈，又回到了入口节点。
　　剩下的问题是如何得到环中节点的数目。我们在前面提到判断一个链表里是否有环时用到了一快一慢两个指针，如果两个指针相遇，则表明链表中有环。两个指针相遇的节点一定是在环中。可以从这个节点出发，一边继续向前移动一边计数，当再次回到这个节点时，就可以得到环中节点数了。
　　可以进行优化的地方：如何得到环中节点的数目n？在判断链表是否有环时用到了一快一慢两个指针，如果它们相遇，则表明链表中有环。相遇时走的快的指针走的步数刚好比走的慢的指针走的步数多n步。这相当于运动学上的追击问题，追上的条件是刚好多走“一圈”，在这里可以在两个指针走的过程中对指针走的步数分别进行计数，当它们相遇时，计数之差就是环中节点的数目。对比书中给出的解法：不用在得到相遇节点之后再走n步得到n。减少了常量级别的时间复杂度。
　　勘误：之前认为在求环中节点数目ｎ时可以利用运动学中的追击问题的特性进行时间复杂度上的优化，但在与同学的讨论中发现之前的思路是错误的，之前认为在判断链表是否有环时用到的一快一慢两个指针相遇的条件是快指针刚好多走"一圈"，但实际上是多走了n圈，之前在思考的过程中将两个指针想象成两个人在操场跑步进行追击，人跑步的相遇条件确实是"一圈"，但两个指针一快一慢的"走"，"擦肩而过"并不叫相遇，只有当两个指针指向同一节点时才是真的相遇。

代码如下：

public ListNode EntryNodeOfLoop(ListNode head) {
    // 得到相遇节点
    ListNode meetingNode = getMeetingNode(head);
    if (meetingNode == null) {
        return null;
    }
    // 计算环中节点总数
    int count = 1;
    ListNode node1= meetingNode.next;
    while (node1 != meetingNode) {
        node1 = node1.next;
        count++;
    }
    // 让node1指针先走count步，node2再与node1一起走
    node1 = head;
    ListNode node2 = head;
    for (int i = 0;i < count;i++) {
        node1 = node1.next;
    }
    while (node1 != node2) {
        node1 = node1.next;
        node2 = node2.next;
    }
    // 相遇点即为环的入口节点
    return node1;
}

private ListNode getMeetingNode(ListNode head) {
    ListNode node1 = head;
    ListNode node2 = head;
    while (node1.next != null && node2.next != null) {
        node1 = node1.next;
        node2 = node2.next.next;
        if (node1 == node2) {
            return node1;
        }
    }
    return null;
}