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

import java.util.HashSet;

/*
 public class ListNode {
    int val;
    ListNode next = null;

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

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //方法一：利用集合元素的唯一性，运行时间大概是80ms
        //特殊值处理,链表为空
//        if(pHead == null){
//            return null;
//        }
//        ListNode head0 = pHead;
//        //创建一个哈希集合，存储对象为ListNode
//        HashSet<ListNode> hashSet = new HashSet<>();
//        //遍历链表，如果在哈希集合中存在该节点，即链表存在环；否则，将该节点添加到哈希集合中
//        while (head0 != null){
//            if(hashSet.contains(head0)){//哈希集合中存在该节点,该节点即为链表中环的入口节点，并返回该节点
//                return head0;
//            }else{//哈希集合中不存在该节点，将该节点添加到哈希集合中
//                hashSet.add(head0);
//            }
//            head0 = head0.next; //节点移动
//        }
//        return null;

        //方法二：利用快慢指针，运行时间大概是60ms
        //特殊值处理,链表为空或者链表的长度为1
        if(pHead == null || pHead.next == null){
            return null;
        }
        ListNode fast = pHead.next.next;  //初始化快指针
        ListNode flow = pHead.next;  //初始化慢指针
        boolean flag = false;  //标记值，如果为true代表是相遇后，反之，代表相遇前
        while (flow != null && fast != null){  //遍历链表，当快慢指针都不为空时，
            if(flow == fast){//如果快慢指针指向同一个节点，则代表有环
                if(flag){//相遇后再次相遇，则此节点为链表环的入口节点
                    return flow;
                }else{
                    fast = pHead;//相遇后，更新快指针指向头节点，满指针原地不动，此后快慢指针每次走一步
                }
                flag = true;
            }else{//如果快慢指针不是指向同一个节点,更新快慢指针
                if(flag){//相遇后，更新快指针指向头节点，满指针原地不动，此后快慢指针每次走一步
                    flow = flow.next;  //慢指针每次走一步
                    fast = fast.next;  //快指针每次走一步
                }else{
                    flow = flow.next;  //慢指针每次走一步
                    fast = fast.next;  //快指针每次走两步
                    if(fast != null){//快指针每次走两步，可能存在刚走完一步就是空指针，所以要验证快指针为非空
                        fast = fast.next;
                    }
                }
            }
        }
        return null;
    }
}