弗洛伊德判圈算法-leetcode142.环形链表II

Problem: 142. 环形链表 II

思路

使用双指针+弗洛伊德算法（龟兔赛跑）

弗洛伊德算法

• 判断是否存在环：类比龟兔赛跑，一快一慢指针，快慢指针会在环内某点相遇
• 判断环的起点：
  
  S慢=a+b
  S快=a+b+L=2S慢
  a+b=L
  因此在第一次相遇时，将快指针置链表起点，速度和慢指针一样，再次相遇在环的起点

解题步骤

• 空链表、单节点链表直接返回null
• 快慢指针判断是否有环
• 相遇说明有环，则将快指针置为head，速度放慢
• 二者再次相遇在起点
• 不满足第一次相遇返回null

复杂度

时间复杂度:

虽然嵌套循环，但节点最多遍历f(n)次： $O(n)$

空间复杂度:

常数大小的额外空间：$O(1)$

Code

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    //判断是否有环
    if(head === null || head.next === null){
        return null;
    }

    let slow = head;
    let fast = head;

    while(fast !== null &&fast.next !== null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast){
            //弗洛伊德算法，快指针返回头部，速度和慢指针一样，二者再次相遇时，恰好在环的起点
            fast = head;
            while(fast !== slow){
                slow = slow.next;
                fast = fast.next;
            }
            return fast;
        }
    }

    return null;
    
};