Daily practice of LeetCode - Circular linked list question (interview four consecutive questions)

前言

Wassup guys！我是Edison

今天是 LeetCode 上的两道题： 141. 环形链表 和 142. 环形链表 II

Let’s get it！

---

---

判断链表是否有环

1. 题目描述

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

示例 1：

示例 2：

示例 3：

2. 思路分析

这道题的思路很简单,还是用 快慢指针;

每当慢指针 slow 前进一步,快指针 fast 就前进两步.
 
如果 fast 最终遇到空指针,说明链表中没有环;
 
如果 fast 最终和 slow 相遇,那肯定是 fast 超过了 slow 一圈,说明链表中含有环.

注意,如果链表没有环：

Linked list if yes 奇数 个,那么 slow 走一步,fast Take two steps,那么 fast Must go 尾节点 ,So the condition to terminate the loop is fast->next != NULL.
 
Linked list if yes 奇数 个,那么 slow 走一步,fast Take two steps,那么 fast Must go NULL 的位置,So the condition to terminate the loop is fast != NULL.

3. 动图演示

准备两个指针 fast 和 slow,循环链表;

slow 指针初始也指向 head,每次循环向前走一步;

fast 指针初始指向 head,每次循环向前两步;

如果没有环,则快指针会抵达终点,如果有环,那么快指针会追上慢指针（动图演示）

4. 代码实现

接口代码

bool hasCycle(struct ListNode *head) {
    
    // 快慢指针初始化指向 head
    struct ListNode* slow = head; 
    struct ListNode* fast = head; 

    // 快指针 Stop when you reach the end
    while (fast && fast->next) {
    
        slow = slow->next; //慢指针走一步
        fast = fast->next->next; //快指针走两步
        // 快慢指针相遇,说明含有环
        if (slow == fast) {
    
            return true;
        }
    }
    // 不包含环
    return false;
}

提交结果

Returns the first node of the linked list into the ring

1. 题目描述

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

示例 1：

示例 2：

示例 3：

2. 思路分析

This is no longer a simple code problem,确切的来说,是 数学公式推导 + 逻辑结合 的一道题.
 
为什么要这样呢？这里简单说一下其中的原理.

Pass the first question above,You have learned to determine whether a linked list has a cycle,那么接下来要找这个环的入口了.

假设从 头结点 to the ring 入口节点 的节点数为 x.

环形 入口节点 到 fast 指针与 slow 指针 相遇节点 节点数为 y.

从 相遇节点 Back to the ring 入口节点 的节点数为 z. （如图所示）

那么相遇时：

slow 指针走过的节点数为:：$x+y$

fast 指针走过的节点数： $x+y+n(y+z)$,n 为 fast 指针在环内走了 n 圈才遇到 slow 指针,$（y+z）$is the number of nodes in a circle.

因为 fast 指针是一步走两个节点,slow 指针一步走一个节点, 所以 $fast指针走过的节点数=slow指针走过的节点数\ast 2$,也就是

$(x+y)\ast 2=x+y+n(y+z)$

Eliminate one on both sides at the same time $(x+y)$,化简得：$x+y=n(y+z)$;

因为我们要找环形的入口,那么要求的是 x,因为 x 表示 头结点 到 Ring entry node 的距离.

所以我们要求 x ,将 x alone on the left：$x=n(y+z)-y$;

在从 $n(y+z)$ 中提出一个 $(y+z)$ 来,整理公式之后为如下公式：$x=(n-1)(y+z)+z$ ;

注意这里 n 一定是大于等于 1 的,因为 fast 指针 Take at least one more lap to meet slow 指针.

这个公式说明什么呢？

先拿 n 为 1 的情况来举例,意味着 fast 指针在环形里转了一圈之后,就遇到了 slow 指针了.

当 n 为 1 的时候,公式就化解为 $x=z$;

这就意味着,从头结点出发一个指针,A pointer is also sent from the encounter node,这两个指针每次只走一个节点, Then when these two pointers meet, it is the node of the ring entry.

也就是在相遇节点处,定义一个指针 index1,在头结点处定一个指针 index2.

让 index1 和 index2 同时移动,每次移动一个节点, Then the place where they meet is the node of the ring entrance. （动图演示）

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

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

3. 简化思路

我们假设 快慢指针相遇 时,慢指针 slow 走了 k 步,那么快指针 fast 一定走了 2k 步（如图所示）

fast 一定比 slow 多走了 k 步,这多走的 k 步其实就是 fast 指针在环里转圈圈,所以 k 的值就是环长度的「整数倍」.

假设 相遇点 距 环的起点 的距离为 m,（见下图）那么 环的起点 from the head node head 的距离为 k - m,也就是说如果从 head 前进 k - m 步就能到达环起点.

如果从相遇点继续前进 k - m 步,也恰好到达环起点.因为结合上图的 fast 指针,从相遇点开始走 k 步可以转回到相遇点,那走 k - m 步肯定就走到环起点了（如图所示）

所以,只要我们把快慢指针中的任一个重新指向 head,然后两个指针同速前进,k - m 步后一定会相遇,相遇之处就是环的起点了

4. 代码实现

接口代码

struct ListNode *detectCycle(struct ListNode *head) {
    
    struct ListNode* slow = head;
    struct ListNode* fast = head;

    while (fast && fast->next) {
    
        slow = slow->next; // 慢指针走一步
        fast = fast->next->next; // 快指针走两步
        // 相遇了
        if (slow == fast) {
    
            struct ListNode* meet = slow;
            while (meet != head) {
    
                meet = meet->next; // 一个指针从出发点开始走
                head = head->next; // 一个指针从出发点开始走 
            }
            // meet和head相等时,What is returned is the entry point
            return meet;
        }
    }
    // 链表不带环
    return NULL;
}

提交结果

扩展追问

The realization of this problem is very simple,But there will be several scaling issues here,需要证明！

（1）slow 一次走 1 步,fast 一次走 2 步,一定能追上吗？
 
（2）slow 一次走 1 步,fast 一次走 3 步,能追上吗？fast 走 4 步呢？或者 fast 走 n 步呢？能追上吗？
 
Answer the two questions above,并证明！

问题一

slow 一次走 1 步,fast 一次走 2 步,一定能追上吗？

假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环.

当慢指针刚进环时,可能就和快指针相遇了,假设 快指针 和 慢指针 之间的距离为 N.

during their movement,The quick pointer moves forward two steps,慢指针走一步,此时,两个指针每移动一次,之间的距离就缩小 1 步,until reduced to 0,Then it means they meet,Therefore, there will not be a situation where it happens to be a ferrule every time,

因此,在慢指针走到一圈之前,快指针肯定是可以追上慢指针的,即相遇.

问题二

slow 一次走 1 步,fast 一次走 3 步,能追上吗？fast 走 4 步呢？或者 fast 走 n 步呢？能追上吗？

as they progress,快指针 每次走 3 步,慢指针 每次走 1 步,此时 快指针 肯定 先进环,慢指针 就 后进环.

假设 慢指针 进环时,快指针 和 慢指针 之间的距离为 N,又因为 快指针 每次走 3 步,慢指针 每次走 1 步,So every time you go,他们之间的距离就缩小 2 .

此时要分 两 种情况：

1、如果 N 为偶数,Then the distance between them will eventually shrink 0,That is to meet.

2、如果 N 为奇数,Then the difference between them will be reduced 1,然后减到 负1,减到 负1 It means that the distance between them has become again C - 1（C 是环的周长）,此时又分为 2 种情况;

2.1、若 C 为奇数,则 C - 1 为偶数,Because the distance between them shrinks at a time 2,So they still meet;

2.2、若 C 为偶数,则 C - 1 为奇数,That is to say, the distance between them is still odd,Then they will never meet.

总结：

当慢指针走一步,快指针走三步时.
 
若 慢指针进环时 与 快指针 之间的距离为 奇数,And the perimeter of the ring is exactly 偶数,那么他们会一直在环里面打转转,永远不会相遇.