本文共 1519 字，大约阅读时间需要 5 分钟。

题目链接：

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例1：

输入：head = [3,2,0,-4], pos = 1输出：tail connects to node index 1解释：链表中有一个环，其尾部连接到第二个节点。

思路：和解法相似，这里先采用快慢指针判断单链表是否有环，如果有环则找寻入环节点。因为快指针走两步，慢指针走一步，因此相同时间内快指针走的路程是慢指针的两倍。如下图： 如上图所示，假设A为入环口，a为链表头到入环口的距离，B为快慢指针第一次相遇的点，b为入环口A到第一次相遇点B的距离(顺时针方向)，c为这个环剩下的距离(也就是B到A的顺时针距离)。 当快慢指针第一次相遇时，慢指针走的距离是a+b，快指针走的距离是a+b+c+b,快指针的速度是满指针的两倍，因此得出等式(a+b+c+b)=2*(a+b)==> c=a,也就是说，现在我们要找入环口位置，只需要慢指针继续走，重新定义一个指针指向头节点，两个指针同步走，相遇时候就是入环口位置.

代码：

/** * Definition for singly-linked list. * class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {
       public ListNode detectCycle(ListNode head) {
           if(head==null||head.next==null) return null;        ListNode fastNode=head;        ListNode slowNode=head;        boolean flag=false;        while(fastNode.next!=null&&fastNode.next.next!=null){
               fastNode=fastNode.next.next;            slowNode=slowNode.next;            if(slowNode==fastNode){
                   flag=true;                break;            }        }        if(flag){
               fastNode=head;            while(fastNode!=slowNode){
                   fastNode=fastNode.next;                slowNode=slowNode.next;            }            return fastNode;        }else{
               return null;        }    }}

扩展：

如果要求环的大小，那么我们只需要从入环口位置出发，一步步移动指针，当再次到达入环口位置则可以计算出换的大小。

转载地址：https://dh-butterfly.blog.csdn.net/article/details/108447534 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！