力扣算法-Day11

142.环形链表II

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

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

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

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2 ：?

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

思路：

这道题目主要分为两步：

1. ?判断链表是否有环
2. ?返回链表入环的第一个节点

判断是否有环，主要是利用快慢指针，快指针每次移动两步，慢指针每次移动一步，一定是快指针先进入环，慢指针后进入环，进入环后快指针相对于慢指针是每次前进一步，这是一个追赶慢指针的过程。最后一定相遇，并且慢指针一定没移动完整个环。

如果有环，如何找到这个环的入口?？

?

假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：

相遇时，慢指针一共走了X+Y步，快指针一共走了X+Y+n(Y+Z)步n>=1;

然而2*(X+Y) = X+Y+n*(Y+Z)? ==>? ? ? ? ?X = (n-1) * (Y+Z) + Z? ? n>=1;

所以说当一个指针从相遇点出发，另一个指针从头节点出发，他们两个一定是在环形入口节点处相遇。

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

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

?

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* low = head;
    struct ListNode* high = head;
    while (high && high->next) {
        high = high->next->next;
        low = low->next;
        if (low == high ) {
            struct ListNode* index1 = head;
            struct ListNode* index2 = low;
            while (index1 != index2) {
                index1 = index1->next;
                index2 = index2->next;
            }
            return index1;
        }
    }
    return NULL;
}

总结：

• 时间复杂度: O(n)，快慢指针相遇前，指针走的次数小于链表长度，快慢指针相遇后，两个index指针走的次数也小于链表长度，总体为走的次数小于 2n
• 空间复杂度: O(1)

这道题目主要考察的还是快慢指针的应用，及数学！

所以说算法的尽头是数学！！！

这一期专栏记录将我每天的刷题，希望各位的监督，也希望和各位共勉。

追光的人，终会光芒万丈！！