题目描述

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

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

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

示例1

输入：
{1,2},{3,4,5}

返回值：
3

说明：
返回环形链表入口节点，我们后台会打印该环形链表入口节点，即3

示例2

输入：
{1},{}

返回值：
"null"

说明：
没有环，返回null，后台打印"null"

从题已知信息

  1. 链表无环输出null

方法一: 哈希法

思路和算法

最容易想到的方法是遍历所有节点，每次遍历到节点时，判断该节点此前是否被访问过。
图片说明
全部代码如下：

import java.util.*;
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode curr = pHead;
        // 用来记录访问过的路径
        Set<ListNode> set = new HashSet<>();
        while(curr!=null){
            //如果有环，则相遇的第一个节点就是入口节点
            if(set.contains(curr)){
                return curr;
            }else{
                //如果没有访问过就加入
                set.add(curr);
            }
            curr = curr.next;
        }
        //无环输出null
        return null;
    }
}

复杂度分析

时间复杂度：O(N) ，遍历一次 O(N) .
空间复杂度：O(N) ，hashset随链表长度增大

方法二：快慢指针

思路和算法

我们使用两个指针，fast 与 slow
如果链表中存在环，则 fast 指针 slow 指针在环中相遇。
如果不存在，fast将会先走到结尾 null
图片说明
根据这个图片，假设在橘色点相遇，我们可以知道 fast指针走的路程为：
fast = a + n ( b + c ) + b // fast 不知道在环中跑多少圈，这里假定 n ， b + c 是一圈的距离

根据题意可知道，2slow = fast, 如果有环的话，slow没跑完一圈必定被fast追上
slow = a + b
a + ( n + 1) b + nc = 2 ( a + b )
(n - 1 ) b + nc = a
nb + nc - b = a // 在补一个 + c - c 可以转换成下面的公式
c + (n - 1) ( b + c )= a

由此知道， 从相遇点开始跑 ， fast 跑 c + (n - 1) ( b + c ) 跟 slow 跑 a 的距离是一样的

  1. 先找出相遇点
  2. 在相遇之后把 slow 归为 0 位置，从头开始跑，此时相遇的点就是入口节点 
import java.util.*;
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast = pHead, slow = pHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            //如果快慢指针相遇了，就是图中的紫色的点
            if (fast == slow) {
                // 慢指针从头在来，他们再次相遇时，就是入口
                slow = pHead;
                while (slow != fast) {
                    fast = fast.next;
                    slow = slow.next;
                    // 找到入口，跳出
                    if (fast == slow) {
                        break;
                    }
                }
                return fast;
            }
        }
        return null;
    }
}

复杂度分析

时间复杂度：O(N)， 遍历2次，大概是 2N次循环 所以是 O(N)
空间复杂度：O(1) ， 常数级，只有2个指针