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

题目主要信息:

• 给定一个链表，首先判断其是否有环，然后找到环的入口

举一反三：

学习完本题的思路你可以解决如下题目：

BM4.合并有序链表

BM5.合并k个已排序的链表

BM6.判断链表中是否有环

BM8.链表中倒数最后k个节点

BM9.删除链表的倒数第n个节点

BM10.两个链表的第一个公共节点

BM13.判断一个链表是否为回文结构

BM14.链表的奇偶重排

方法：双指针（推荐使用）

知识点：双指针

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。

思路：

根据题干，不说别的，我们能发现这道题需要完成两个任务：

1. 判断链表是否有环。
2. 在有环的链表中找到环的入口。

对于第一个任务，可以参考判断链表中是否有环，主要思想是利用环没有末尾NULL，后半部分一定是环，然后快慢双指针相遇就代表有环。（具体分析可以参考BM6.判断链表中是否有环）

那我们现在假定已经是一个有环的链表了，那么这个链表中怎么找到环的入口呢？在慢指针进入链表环之前，快指针已经进入了环，且在里面循环，这才能在慢指针进入环之后，快指针追到了慢指针，不妨假设快指针在环中走了$nn$圈，慢指针在环中走了$mm$圈，它们才相遇，而进入环之前的距离为$xx$，环入口到相遇点的距离为$yy$，相遇点到环入口的距离为$zz$。快指针一共走了$x+n(y+z)+yx+n(y+z)+y$步，慢指针一共走了$x+m(y+z)+yx+m(y+z)+y$，这个时候快指针走的倍数是慢指针的两倍，则$x+n(y+z)+y=2(x+m(y+z)+y)x+n(y+z)+y=2(x+m(y+z)+y)$，这时候$x+y=(n-2m)(y+z)x+y=(n-2m)(y+z)$，因为环的大小是$y+zy+z$，说明从链表头经过环入口到达相遇地方经过的距离等于整数倍环的大小：那我们从头开始遍历到相遇位置，和从相遇位置开始在环中遍历，会使用相同的步数，而双方最后都会经过入口到相遇位置这$yy$个节点，那说明这$yy$个节点它们就是重叠遍历的，那它们从入口位置就相遇了，这我们不就找到了吗？

具体做法：

• step 1：使用BM6.判断链表中是否有环中的方法判断链表是否有环，并找到相遇的节点。
• step 2：慢指针继续在相遇节点，快指针回到链表头，两个指针同步逐个元素逐个元素开始遍历链表。
• step 3：再次相遇的地方就是环的入口。

图示：

Java实现代码：

public class Solution {
    //判断有没有环，返回相遇的地方
    public ListNode hasCycle(ListNode head) {
        //先判断链表为空的情况
        if(head == null) 
            return null;
        //快慢双指针
        ListNode fast = head; 
        ListNode slow = head;
        //如果没环快指针会先到链表尾
        while(fast != null && fast.next != null){ 
            //快指针移动两步
            fast = fast.next.next; 
            //慢指针移动一步
            slow = slow.next; 
            //相遇则有环，返回相遇的位置
            if(fast == slow) 
                return slow;
        }
        //到末尾说明没有环，返回null
        return null; 
    }
    
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = hasCycle(pHead);
        //没有环
        if(slow == null) 
            return null;
        //快指针回到表头
        ListNode fast = pHead; 
        //再次相遇即是环入口
        while(fast != slow){ 
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

C++实现代码：

class Solution {
public:
    //判断有没有环，返回相遇的地方
    ListNode* hasCycle(ListNode *head) { 
        //先判断链表为空的情况
        if(head == NULL) 
            return NULL;
        //快慢双指针
        ListNode* fast = head; 
        ListNode* slow = head;
        //如果没环快指针会先到链表尾
        while(fast != NULL && fast->next != NULL){ 
            //快指针移动两步
            fast = fast->next->next; 
            //慢指针移动一步
            slow = slow->next; 
            //相遇则有环
            if(fast == slow) 
                //返回相遇的地方
                return slow; 
        }
        //到末尾则没有环
        return NULL; 
    }
    
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* slow = hasCycle(pHead);
        //没有环
        if(slow == NULL) 
            return NULL;
        //快指针回到表头
        ListNode* fast = pHead; 
        //再次相遇即是环入口
        while(fast != slow){ 
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

Python代码实现：

class Solution:
    #判断有没有环，返回相遇的地方
    def detectCycle(self, pHead: ListNode):
        slow = self.hasCycle(pHead)
        #没有环
        if slow == None: 
            return None
        #快指针回到表头
        fast = pHead 
        #再次相遇即是环入口
        while fast != slow: 
            fast = fast.next
            slow = slow.next
        return slow
    
    def hasCycle(self , head):
        #先判断链表为空的情况
        if head == None: 
            return None
        #快慢双指针
        fast = head 
        slow = head
        #如果没环快指针会先到链表尾
        while fast != None and fast.next != None: 
            #快指针移动两步
            fast = fast.next.next 
            #慢指针移动一步
            slow = slow.next 
            #相遇则有环
            if fast == slow: 
                #返回相遇的地方
                return slow 
        #到末尾则没有环
        return None 

复杂度分析：

• 时间复杂度：$O(n)O(n)$，最坏情况下遍历链表两次
• 空间复杂度：$O(1)O(1)$，使用了常数个指针，没有额外辅助空间