Day10——链表专题

不念不忘少年蓝@ 2024-04-03 13:07 86阅读 0赞

#### 20.环形链表II ####

**快慢指针：**

![image-20221016203018845][]

因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 \* 2：

(x + y) * 2 = x + y + n (y + z)  经过化简之后 x = (n - 1) (y + z) + z，当n=0时，x=z;

因为快指针一定会在慢指针没走一圈，就会追赶到。当两个指针下次相遇时，一定在相遇节点处，定义一个指针index1，在头结点处定一个指针index2，index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。

**那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。**

其实这种情况和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。

public class Solution {
        
        public ListNode detectCycle(ListNode head) {
        
            ListNode slow = head;
            ListNode fast = head;
            while (fast != null && fast.next != null) {
        
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
        // 有环
                    ListNode index1 = fast;
                    ListNode index2 = head;
                    // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                    while (index1 != index2) {
        
                        index1 = index1.next;
                        index2 = index2.next;
                    }
                    return index1;
                }
            }
            return null;
        }
    }

[image-20221016203018845]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/5a018ca591e7493db886a44090a0611a.png