题解 | #链表中环的入口结点#

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //先判断是否有环，无环返回null
        if (hasCycle(pHead)) {
            List<ListNode> listNodeList  = new ArrayList<>();
            ListNode cycleEntryNode = null;
            while (pHead != null) {
                ListNode temp = pHead;
                listNodeList.add(temp); //将遍历的节点放入该List中，方便后续操作
                pHead = pHead.next;
                if (listNodeList.contains(pHead)) { //若List中保存的节点再次且首次出现，
                    cycleEntryNode = pHead;         //则该节点为链表中环的入口节点
                    break;
                }
            }
            return cycleEntryNode;
        }
        return null;
    }

    public boolean hasCycle(ListNode head) {
        ListNode fastNode = head;
        ListNode slowNode = head;
        while (fastNode != null && fastNode.next != null) {
            fastNode = fastNode.next.next;
            slowNode = slowNode.next;
            if (fastNode == slowNode) {
                return true;
            }
        }
        return false;
    }
}

思路：

1、先判断是否有环，使用快慢指针来判断，无环返回null，有环则继续

2、对有环的链表进行遍历，将遍历过的节点放入一个List中，若List中保存的节点再次且首次出现，则该节点为链表中环的入口节点