55、链表中环的⼊⼝节点

题⽬描述

给⼀个链表，若其中包含环，请找出该链表的环的⼊⼝结点，否则，输出null 。

例如，输⼊{1,2},{3,4,5} 时，对应的环形链表如下图所示：

可以看到环的⼊⼝结点的结点值为3，所以返回结点值为3的结点。

给定的链表节点的结构：

public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
    	this.val = val;
    }
}

思路及解答

借用HashSet

第⼀种是直接使⽤ HashSet ,遍历链表的时候，如果 HashSet 中不包含，则添加到 HashSet 中，如果链表中包含，说明已经回到环的第⼀个节点。Java 代码实现如下：

public ListNode EntryNodeOfLoop(ListNode pHead) {
    HashSet set = new HashSet();
    while(pHead!=null){
        if(set.contains(pHead)){
        	return pHead;
        }else{
            set.add(pHead);
            pHead = pHead.next;
        }
    }
    return null;
}

双指针

上⾯的做法时间复杂度为O(n) ，由于借助了⼀个hashSet ，空间复杂度也为O(n) 。那假设我们不需要使⽤额外的空间呢？怎么做呢？

使⽤快慢双指针，⼀个⼀次⾛⼀步，⼀个⼀次⾛两步，当两个重合在⼀起的时候，这时候，并不是环的⼊⼝节点。只能说明两个指针，⼀个⽐另外⼀个多⾛了若⼲圈，可能是⼀圈，可能是2 ， 3 圈。

⽐如上⾯的，如果开始节点是A ，环的⼊⼝是B ，相遇的节点是C ，那么

• 慢指针⾛的距离是： S=AB+BC
• 快指针⾛的距离是： 假设多⾛了n圈，2S = AB+(BC+CB)*n+BC ，

即 2(AB+BC) = AB+(BC+CB)*n+BC，也就是AB+BC = (BC+CB)*n

假设n =1 ，那么AB = CB ,也就是当前位置到环的⼊⼝的⻓度，等于链表头到环的⼊⼝的位置。

因此相遇之后，我们将⼀个快指针移动到链表头，两个指针每次⼀步，直到相遇，这个时候，相遇的节点就是环的⼊⼝节点。

public ListNode EntryNodeOfLoop(ListNode pHead) {
    ListNode quick = pHead;
    ListNode slow = pHead;
    while (quick != null && slow.next != null) {
        quick = quick.next;
        slow = slow.next.next;
        if (quick == slow) {
            quick = pHead;
            while (quick != slow) {
                quick = quick.next;
                slow = slow.next;
            }
            return quick;
        }
    }
    return null;
}

时间复杂度： O(n) 空间复杂度： O(1)