【基础篇 - Day 11】 2023-02-23 - 142. 环形链表 II （02. 链表 ）

[threedayAAAAA]

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

 

示例 1：

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

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

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

提示：

链表中节点的数目范围在范围 [0, 104] 内 -105 <= Node.val <= 105 pos 的值为 -1 或者链表中的一个有效索引  

进阶：你是否可以使用 O(1) 空间解决此题？

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/linked-list-cycle-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[threedayAAAAA]

思路

• 定义⼀个 fast 指针,每次前进两步,⼀个 slow 指针,每次前进⼀步
• 当两个指针相遇时
• 1. 将 fast 指针指向链表头部,同时 fast 指针每次只前进⼀步
• 2. slow 指针继续前进,每次前进⼀步
• 当两个指针再次相遇时,当前节点就是环的⼊⼝

为什么第⼆次相遇的点为环的⼊⼝? 原因如下： 第⼀次相遇时

• 慢指针移动的距离为 s1 = A + B + n1 * L
• 快指针移动的距离为 s2 = A + B + n2 * L
• 快指针是慢指针速度的两倍,所以 s2 = 2* s1
• A + B + n2 L = 2A + 2B + n1 L ===> A = -B + (n2 - n1) * L
• 因为圆的性质 (n2 - n1) * L ===> 绕圆 (n2 - n1) 圈 ===> 0
• A = -B + (n2 - n1) * L ===> A = -B
• 即在第⼀次相遇点, 向前⾛ A 步 ===> 向后⾛ B 步

第⼀次相遇后

• 快指针从头节点⾛ A 步会到达环的⼊⼝
• 慢指针从第⼀次相遇点⾛ A 步,相当于向后⾛ B 步,也会到达环的⼊⼝

代码

function detectCycle(head: ListNode | null): ListNode | null {
    let fast = head
    let slow = head
    do {
        fast = fast?.next?.next ?? null
        slow = slow?.next ?? null
    } while(fast !== slow) 
    if(fast === null){
        return fast
    }
    fast = head;
    while (fast !== slow) {
        fast = fast.next;
        slow = slow.next;
    } 
    return fast
};

时空复杂度

• 时间复杂度： O(n)
• 空间复杂度：O(1)

[yunliuyan]

思路

• 快慢指针
• 当快指针和慢指针相遇后，head和慢指针相遇就是交点

代码

function detectCycle(head: ListNode | null): ListNode | null {
    let slow = head, fast = head;
    while(fast?.next?.next) {
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast) {
            while(head !== slow) {
                head = head.next;
                slow = slow.next;
            }
            return slow;
        }
    }
    return null;
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[MiumMi]

思路

遇到求环结点的，一般两种方法，一个是哈希表记录已经走过的节点，一个是快慢指针。针对这个题，要求空间复杂度是O(1)，所以只能用快慢指针的方法来实现，直接套模板就好

代码

function detectCycle(head: ListNode | null): ListNode | null {
    if (!head || !head.next) {
        return null;
    }
    let fast = head;
    let slow = head;
    do {
        if (fast?.next) {
            fast = fast.next.next;
        } else {
            fast = null;
        }
        slow = slow.next;
    } while (fast !== slow)
    if (!fast) {
        return null;
    }
    fast = head;
    while(fast !== slow) {
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
};

---

分析

1. 时间复杂度：O(n)
2. 空间复杂度：O(1)