[数据结构与算法]环形链表 II 快慢指针法 + 哈希表法

环形链表 II 快慢指针法 + 哈希表法

链接：https://leetcode-cn.com/problems/linked-list-cycle-ii/

1. 题目要求

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

为了表示给定链表中的环，我们使用整数 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
解释：链表中没有环。

2.快慢指针法：

算法分析：

1.定义两个指针 fast 和 slow 同时指向 head ，fast 每次走2步，slow 每次走一步。

2.第一次相遇时，假设开头到环的节点个数为 a， 环走一圈的节点个数为 b。

• fast走到链表的末端，fast == NULL，说明链表无环。

• 假设 fast 指针走了 f 步，slow 指针走了 s 步。由第一步知：

$$f=2s$$

若 fast 和 slow 第一次相遇，则：fast比slow多走 n 个环。如上图所示：

$$f=s+nb$$
2（2）-（1）: $f=2nb$

(1) - (2) : $s=nb$

即第一次相遇时， fast 和 slow 分别走了 2n 和 n 个周长。

3.目前情况分析：

如上图所示，假如在 环里 6 这个节点相遇：

假如让指针一直走，并统计步数 k ，开始指针指向head节点，则走到环形节点入口时， $k=a+nb$, 相当于，走了a步，或者对于环形 b 又多绕了 n 圈。

现在slow已经走了 nb 圈，此时只需要 把fast 节点重新指向 head 节点，然后fast每次走一步,当 slow 走了 $nb+a$ 步时，fast 走了 $a$ 圈，此时 fast 和 slow 刚好在环形入口处，返回此时的地址即可。

3.C语言实现代码如下：

struct ListNode *detectCycle(struct ListNode *head) {
    // 1.定义fast、slow指针同时指向head，fast每次走2步，slow每次走1步；
    struct ListNode *fast = head;
    struct ListNode *slow = head;
    //2.如果fast走过链表末端，说明链表无环。
    while(1){
        if(fast == NULL || fast->next == NULL)
            return NULL;
        fast = fast->next->next;	//fast 每次走2步
        slow = slow->next;		   //slow 每次走1步
        if(fast == slow)
            break;
    }
    // 3.双指针第二次相遇
    fast = head;
    while(fast != slow){
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

4. 哈希表法(hash table)

算法思路：

遍历环形链表，每次遍历的元素都使用 hash table 记录下来，比较该元素是否在 Hash Table 中，如果在，则返回索引（此时就找到了环形表的开头元素），否则把该元素添加到集合中，然后进行遍历。

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        temp = head;
        mySet = set()		# 定义集合用来存储
        while temp is not None:
            if temp in mySet:	# 判断一个元素是否在集合中 ， 使用 in 即可。
                return temp
            else:
                mySet.add(temp)
            temp = temp.next
        return None