剑指offer16

题目描述

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

解题思路分析

• 首先我们应该判断链表中是否有环，利用一个快慢指针，如果快指针最后还碰上了慢指针就说明链表中有环
• 然后我们需要找到环的入口节点，利用前面一步找到的环，当然前面肯定是在环中相遇的，所以利用前面找到的环中的节点，先计算出环的长度，然后使一个指针先从头走环的长度那么长，然后使另一个指针从头开始走，最后两个指针会相遇在环的入口节点。

代码实现

public ListNode entryNodeOfLoop(ListNode pHead) {
    if (pHead == null) {
        return null;
    }
    //先找到环中的某个节点
    ListNode meetingNode = meetingNode(pHead);
    int count = 1;
    ListNode node = meetingNode;
    //计算环中的节点个数
    while (node.next != meetingNode) {
        count++;
        node = nodex.next;
    }
    ListNode node1 = pHead, node2 = pHead;
    //先让一个节点走节点个数步
    for (int i = 0; i < count; i++) {
        node1 = node1.next;
    }
    //开始找到环的入口节点
    while (node1 != node2) {
        node1 = node1.next;
        node2 = node2.next;
    }
    return node2;
}

//返回环中的节点
public ListNode meetingNode(ListNode pHead) {
    //分别声明快指针和慢指针
    ListNode slow = pHead, fast = pHead.next;
    while (fast != null) {
        if (fast == slow) {
            return fast;
        }
        slow = slow.next;
        fast = fast.next;
        //防止空指针异常
        if (fast != null) {
            fast = fast.next;
        }
    }
    return null;
}