题目

描述

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

输入描述：

输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台将这2个会组装成一个有环或者无环单链表

返回值描述：

返回链表的环的入口结点即可。而我们后台程序会打印这个节点

算法一 暴力解

• 判断链表中环的入口节点， 即如果把链表中所有节点都存入一个list那么只要判断list.contains(node)为true即可以得知, 因为调用了contains,算法复杂度为O( ,空间复杂度为O(n)

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        List<ListNode> list = new ArrayList<>();
        while (pHead != null){
            //当第一次list.contains(pHead)为ture时即为链表中环的入口节点
            if (list.contains(pHead)){
                return pHead;
            }
            list.add(pHead);
            pHead=pHead.next;
        }
        return null;
    }

算法二 运用数学思维， 快慢指针

• 使用快慢指针，即fast指针每次走两步，slow指针每次走一步，同时都环入口节点出发。a 为从根节点到环入口节点的长度，R为环的周长，M点为环入口节点，N为快慢指针相遇节点，MN为从M点逆时针到N点的距离
• 当快慢指针在N相遇可以得到 fast = a + nR + MN , slow = a + MN
• 又因为fast = 2slow
• 所以可以得到 2（a + nR + MN） = a + MN
• 即 a = ｎR - MN，　那么令ｎ＝１，即可以得到　ａ＝Ｒ－ＭＮ
• 整个算法的时间复杂度为O(n),空间复杂度为O(1)

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null){
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        while (fast.next != null && slow.next != null){
            // fast每次走两步，slow每次走一步
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                break;
            }
        }
        if(fast.next == null){
            // 如果fast.next == null 即链表中没有环
            return null;
        }
        ListNode head = pHead;
        if(head == fast){
            // 这种情况下表示a长度为0
            return head;
        }
        while (head != null && fast != null){
            head = head.next;
            fast = fast.next;
            // 当fast与slow再次相遇即表示环节点
            if (head == fast) {
                return head;
            }
        }
        return null;
    }