描述

给定一个链表，如果链表中存在环，则返回到链表中环的起始节点，如果没有环，返回 null 。

在线评测地址

样例 1

输入：null,no cycle 输出：no cycle 解释： 链表为空，所以没有环存在。 

样例 2

输入：-21->10->4->5，tail connects to node index 1 输出：10 解释： 最后一个节点 5 指向下标为 1 的节点，也就是 10，所以环的入口为 10 。 

算法思路：

Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Follow up: Can you solve it without using extra space?

考点：

• 双指针链表判环

题解：

• 使用双指针判断链表中是否有环，慢指针每次走一步，快指针每次走两步，若链表中有环，则两指针必定相遇。
• 假设环的长度为 l，环上入口距离链表头距离为 a，两指针第一次相遇处距离环入口为 b，则另一段环的长度为 c=l-b，由于快指针走过的距离是慢指针的两倍，则有 a+l+b=2*(a+b),又有 l=b+c，可得 a=c，故当判断有环时(slow==fast)时，移动头指针，同时移动慢指针，两指针相遇处即为环的入口。

/**  * Definition for ListNode.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int val) {  *         this.val = val;  *         this.next = null;  *     }  * }  */  public class Solution {     public ListNode detectCycle(ListNode head) {         if (head == null || head.next==null) {             return null;         }          ListNode fast, slow;         fast = head.next;                        //快指针         slow = head;                                //慢指针         while (fast != slow) {                //快慢指针相遇             if(fast==null || fast.next==null)                 return null;             fast = fast.next.next;             slow = slow.next;         }                   while (head != slow.next) {  //同时移动 head 和慢指针             head = head.next;             slow = slow.next;         }         return head;                                //两指针相遇处即为环的入口     } } 

更多题解参考

大佬有話說 (0)