链表中环的入口节点.md

题目描述

如果一个链表中包含环，如何找出环的入口节点？例如，在如下图所示的链表中，环的入口节点是节点3。

测试用例

• 功能测试（链表中包含或者不包含环；链表中有多个或者只有一个节点）
• 特殊输入测试（链表头节点为空指针）

题目考点

• 考察应聘者对链表的理解。
• 考察应聘者所写代码的鲁棒性（考虑的全面性）。
• 考察应聘者分析问题的能力。把一个问题分解成多个简单的步骤，是一种常用的解决复杂问题的方法。

解题思路

1. 确定一个链表中包含环

用两个指向头节点指针，同时从链表的头节点触发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就包含环，如果的走得快的指针走到了链表的末尾都没有追上走得慢的指针，那么链表就不包含环。

2. 找到环的入口

用两个指向头节点指针P1，P2，如果链表中的环有n个节点，则一个指针P1指针先向前移动n步，然后两个指针以相同的数据向前移动。当P2指向指向环的入口节点时，P1已经围绕环走了一圈，又回到了入口节点。

自己解题

没思路（两个指针还能这么用，wtf）

参考解题

/**
 * 链表中环的入口节点
 *
 * @Author rex
 * 2018/7/27
 */
public class Solution {

    /**
     * 获得入口节点
     * @param head
     * @return
     */
    public ListNode EntryNodeOfLoop(ListNode head) {
        ListNode meetingNode = meetingNode(head);
        if (meetingNode == null) {
            return null;
        }

        // 得到环中节点的数目
        int nodesInLoop = 1;
        ListNode node = meetingNode;
        while (node.next != meetingNode) {
            node = node.next;
            nodesInLoop++;
        }
        ListNode p1 = head;
        ListNode p2 = head;
        // 先移动p1，次数为环中节点的个数
        for (int i = 0; i < nodesInLoop; i++) {
            p1 = p1.next;
        }
        // 再同时移动p1，p2，当p1 = p2时，即为入口节点
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }

    /**
     * 在存在环的前提下找到一快一慢两个指针相遇的节点
     * 没有找到则代码不存在环
     * @param head
     * @return
     */
    public ListNode meetingNode(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head.next;
        ListNode fast = slow.next;
        while (slow != null && fast != null) {
            if (slow == fast) {
                return fast;
            }
            slow = slow.next;
            fast = fast.next;
            // 增强鲁棒性
            if (fast.next != null) {
                fast = fast.next;
            }
        }
        return null;
    }

}

补充

链表问题多考虑各种花样的双指针用法。