LeetCode | 141 linked list cycle

https://github.com/dolphinmind/datastructure/tree/datastructure-linkedlist

分析

证明过程

基本假设

• 假设环的长度为(C)
• 假设从链表的头部到环的入口点的距离为(A)
• 假设从环的入口点到快慢指针第一次相遇点的距离为(B)
• 假设从快慢指针第一次相遇点回到环的入口点的距离为(C-B)

证明过程

1. 慢指针的移动

• 慢指针每次移动一步
• 当慢指针进入环后，它会沿着环移动，直到与快指针相遇

2. 快指针的移动

• 快指针每次移动两步
• 当快指针进入环后，它也会沿着环移动，直到与慢指针相遇

3. 相遇点分析

• 当快指针和慢指针相遇时，假设慢指针走了(x)步，那么快指针走了(2x)步
• 慢指针从链表头部到相遇点的距离为(A+B+rC),其中(r)是慢指针在环内绕圈的次数
• 快指针从链表头部到相遇点的距离为(A+B+kC)，其中(k)是快指针在环内绕圈的次数
• 因为快指针的速度是慢指针的两倍，所以快指针走的距离是慢指针的两倍，即2(A+B+rC) = A+B+kC

4. 求解方程

• 从上述方程可以得出A + B + rC = |k-r|C => A + B = C + hC
• 这意味着慢指针走过的距离 (A+B+rC)是环长度(C)的整数倍
• 由于 (A+B+rC)是慢指针从链表头部到相遇点的距离，而(|k-r|C)是快指针在环内绕圈的总长度，这意味着快指针和慢指针在环内相遇

这时可以发现快指针离环入口只需要走(C-B) + hC 距离，与链表的头部到环入口距离一致，将快指针回填到链表头部，类似于尾对齐发，即找到了相交点

主类

package com.github.dolphinmind.linkedlist;

import com.github.dolphinmind.linkedlist.uitls.ListNode;

/**
 * @author dolphinmind
 * @ClassName LinkedListCycle
 * @description 141. 环形链表
 * @date 2024/8/4 slow的速度v = 1
 *                fast的速度v = 2
 *                在没有环的情况下，fast会最先到达末尾，从而返回false
 *                在有环的情况下,  fast在未进入环之前的情况和上述类似，fast进入环之后，fast开始在环内转圈
 *                直到slow也进入圈内，两者的相对速度为v = 1，此时fast指针反追击slow，直到fast追击到slow为止
 *                刚刚在思考的时候，突然想起链表相交的问题：发觉160链表相交问题与当前141环形链表问题有一定的相似性
 *
 *                假设 headA = 1->2->3->4
 *                    headB = 5->6->7->8->9->4
 *
 *                    slow  = 1->2->3->4->5->6->7->8->9->4
 *                    fast  = 5->6->7->8->9->4->1->2->3->4
 *
 *                  head = 1->2->3->4->5->6->7->8->4
 *                  slow = 1->2->3->4->5->6->7->8->4->5->6
 *                  fast = 1->3->5->7->4->6->8->5->7->4->6
 */

public class LinkedListCycle {

    /**
     * 双指针法
     * @param head
     * @return
     */
    public boolean hasCycleTowPointer(ListNode<?> head) {

        if (head == null || head.next == null) {
            return false;
        }

        ListNode<?> slow = head;
        ListNode<?> fast = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (slow == fast) {
                return true;
            }
        }

        return false;

    }



}