描述

题目描述

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

输入描述：

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

返回值描述：

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

示例

输入：{1,2},{3,4,5}
返回值：3
说明：返回环形链表入口节点，我们后台会打印该环形链表入口节点，即3    

引言

记住一点：遇到链表题目要画图

知识点：链表、双指针
难度：⭐⭐⭐

题解

解题思路

通过画图，可以得出基本思路和整个过程。

接着运用快慢指针，通过对路径的对比和计算，以及第二次相遇后，两指针刚好路程相差环长度的n倍

方法一：快慢双指针

图解

算法流程：

• 我们假设 a为出发点到环入口长度，b为环长度
• fast速度是slow 的两倍，当相遇时，设走过的路径长度为：slow = s ，fast = s + nb，即fast比slow多走了n圈环
• 因为时间相同，fast速度为slow两倍，路径自然是slow的两倍，因此：2s = s + nb, 即 s = nb，
• 因为速度不同，肯定能相遇，所以当第一次相遇时，slow走了nb步，fast走了2nb
• 相遇后，让 fast重新从出发点按slow指针相同速度走
• 因为此时 slow 已经走了 nb 的路程，fast走了2nb路程
• 而正常情况走到环入口，最少需要走: a + b，目前slow走了nb步了，需要再走a步就能从相遇点走到环入口节点
• 而当fast是从起点重新走到入口节点，刚好也是路程 a，刚好再次相遇，也就是刚好走到入口节点
• 总的路程：slow = a + nb， fast = a + 2nb，刚好满足在入口节点相遇的路程
• 很重要的一点：指针在走的过程中，从起点走到环里后，会一直在环里转圈

Java 版本代码如下：

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = pHead, fast = pHead;
        while(true) {
            if(fast == null || fast.next == null) {
                // fast先走到null表示无环
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            // 第一次相遇
            if(slow == fast) {
                break;
            }
        }
        // fast从出发点重新开始
        fast = pHead;
        // 第二次相遇
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;        
    }
}

Python 版本代码如下：

class Solution:
    def EntryNodeOfLoop(self, pHead):
        fast, slow = pHead, pHead
        while fast and fast.next:
            fast = fast.next.next  
            slow = slow.next  
            # 第一次相遇
            if fast and fast == slow: 
                # 从出发点重新开始
                slow = pHead  
                # 第二次相遇
                while fast != slow:  
                    fast = fast.next
                    slow = slow.next
                return fast
        return None

复杂度分析：

时间复杂度 O(N)
空间复杂度 O(1)：指针为常数级别空间

总结：链表题多画图

方法二：哈希

解题思路：

只有入口节点才会重复走过，因此用hash记录走过的节点

Java 版本代码如下：

import java.util.*;
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        Set<ListNode> set = new HashSet<>();
        ListNode node = pHead;
        set.add(node);
        while(node!=null){
            node = node.next;
            // 只有入口节点才会重复走过
            if(set.contains(node)){
                break;
            }else
                set.add(node);
        }
        return node;
    }
}

复杂度分析：

时间复杂度 O(N)
空间复杂度 O(N)：哈希需要N级别的空间