一、面试问题给定一个单链表的头节点判断链表中是否存在环。如果在通过next指针遍历链表的过程中再次访问到了已经访问过的节点而非最终到达nullptr则说明链表中存在环。示例 1输入head: 1 - 3 - 4 - 3输出: true解释链表的尾节点不指向空值而是指向链表中靠前的某个节点从而形成环。示例 2Input: head: 1 - 8 - 3 - 4 - NULLOutput: false解释链表的尾节点指向空代表链表结束。二、【朴素解法】使用哈希集合 —— 时间复杂度 O (n)空间复杂度 O (n)(一) 解法思路核心思路在遍历链表的同时将节点存入哈希集合如果遇到一个已经存在于集合中的节点说明链表中存在环直接返回true如果遍历到空节点说明已到达链表末尾不存在环返回false。(二) 使用 5 种语言实现1. C#include iostream #include unordered_set using namespace std; class Node { public: int data; Node* next; Node(int x) { this-data x; this-next nullptr; } }; bool detectLoop(Node* head) { unordered_setNode*st; while (head ! nullptr) { // 如果这个节点已经在哈希集合中存在 // 说明链表中存在环 if (st.find(head) ! st.end()) return true; // 如果是第一次看到该节点将其插入哈希集合 st.insert(head); head head-next; } return false; } int main() { Node* head new Node(1); head-next new Node(3); head-next-next new Node(4); head-next-next-next head-next; if (detectLoop(head)) cout true; else cout false; return 0; }2. Javaimport java.util.HashSet; class Node { int data; Node next; Node(int x) { this.data x; this.next null; } } class DSA { static boolean detectLoop(Node head) { HashSetNode st new HashSet(); while (head ! null) { // 如果该节点已存在于哈希集合中 // 说明存在环 if (st.contains(head)) return true; // 如果是第一次访问该节点将其加入哈希集合 st.add(head); head head.next; } return false; } public static void main(String[] args) { Node head new Node(1); head.next new Node(3); head.next.next new Node(4); head.next.next.next head.next; if (detectLoop(head)) System.out.println(true); else System.out.println(false); } }3. Pythonclass Node: def __init__(self, x): self.data x self.next None def detectLoop(head): st set() while head is not None: # 如果该节点已存在于集合中 # 说明链表中存在环 if head in st: return True # 如果是第一次访问该节点将其加入集合 st.add(head) head head.next return False if __name__ __main__: head Node(1) head.next Node(3) head.next.next Node(4) head.next.next.next head.next if detectLoop(head): print(true) else: print(false)4. C#using System; using System.Collections.Generic; class Node { public int data; public Node next; public Node(int x) { this.data x; this.next null; } } class DSA { static bool detectLoop(Node head) { HashSetNode st new HashSetNode(); while (head ! null) { // 如果该节点已存在于哈希集合中 // 说明存在环 if (st.Contains(head)) return true; // 如果是第一次访问该节点将其加入哈希集合 st.Add(head); head head.next; } return false; } static void Main() { Node head new Node(1); head.next new Node(3); head.next.next new Node(4); head.next.next.next head.next; if (detectLoop(head)) Console.WriteLine(true); else Console.WriteLine(false); } }5. JavaScriptclass Node { constructor(x) { this.data x; this.next null; } } function detectLoop(head) { const st new Set(); while (head ! null) { // 如果该节点已存在于集合中 // 说明链表中存在环 if (st.has(head)) return true; // 如果是第一次访问该节点将其加入集合 st.add(head); head head.next; } return false; } // Driver Code let head new Node(1); head.next new Node(3); head.next.next new Node(4); head.next.next.next head.next; if (detectLoop(head)) console.log(true); else console.log(false);(三)代码输出和算法复杂度输出true时间复杂度O(n)空间复杂度O(n)三、【最优解法】使用弗洛伊德环查找算法快慢指针法—— 时间复杂度 O(n)空间复杂度 O(1)(一) 解法思路该思路是使用弗洛伊德环查找算法寻找链表中的环。算法使用慢指针和快指针两个指针快指针每次移动两步慢指针每次移动一步。算法使用两个指针遍历链表。一个指针慢指针每次移动一步另一个指针快指针每次移动两步。如果这两个指针相遇在同一个节点则说明链表中存在环如果指针始终不相遇则说明链表没有环。以下是上述算法的图解说明为什么链表存在环时快慢指针必定相遇设m 为环起始位置之前的节点数量c 为环的长度环内的节点总数。当两个指针都进入环内后此时快指针与慢指针的步数差每轮增加 1因为每轮循环快指针比慢指针多走 1 步。由于指针在环内循环绕行位置差值需要对环长 c 取模。数学推导设 d 为两指针的位置差对 c 取模则每轮遍历满足d≡d1(modc)由于 1 与 c 互质持续累加 1 会遍历 0,1,2,…,c−1 所有余数。最终必然出现 d≡0代表两指针位置重合即快慢指针相遇。(二) 使用 6 种语言实现1. C#include iostream using namespace std; class Node { public: int data; Node* next; Node(int x) { this-data x; this-next nullptr; } }; bool detectLoop(Node* head) { // 快慢指针 // 初始时都指向头节点 Node *slow head, *fast head; // 循环条件快慢指针均不为空且快指针的下一个节点也不为空 while (slow fast fast-next) { slow slow-next; fast fast-next-next; // 如果快慢指针指向同一个节点说明检测到环 if (slow fast) { return true; } } return false; } int main() { Node* head new Node(1); head-next new Node(3); head-next-next new Node(4); head-next-next-next head-next; if (detectLoop(head)) cout true; else cout false; return 0; }2. C#include stdbool.h #include stdio.h #include stdlib.h struct Node { int data; struct Node* next; }; struct Node* createNode(int new_data) { struct Node* new_node (struct Node*)malloc(sizeof(struct Node)); new_node-data new_data; new_node-next NULL; return new_node; } int detectLoop(struct Node* head) { // 快慢指针初始时都指向头节点 struct Node *slow head, *fast head; // 循环条件快慢指针均不为空且快指针的下一个节点也不为空 while (slow fast fast-next) { slow slow-next; fast fast-next-next; // 如果快慢指针指向同一个节点说明检测到环 if (slow fast) { return true; } } return false; } int main() { struct Node* head createNode(1); head-next createNode(3); head-next-next createNode(4); head-next-next-next head-next; if (detectLoop(head)) printf(true); else printf(false); return 0; }3. Javaclass Node { int data; Node next; public Node(int x) { this.data x; this.next null; } } class DSA { static boolean detectLoop(Node head) { // 快慢指针初始时都指向头节点 Node slow head, fast head; // 循环条件快慢指针均不为空且快指针的下一个节点也不为空 while (slow ! null fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; // 如果快慢指针指向同一个节点说明检测到环 if (slow fast) { return true; } } return false; } public static void main(String[] args) { Node head new Node(1); head.next new Node(3); head.next.next new Node(4); head.next.next.next head.next; if (detectLoop(head)) System.out.println(true); else System.out.println(false); } }4. Pythonclass Node: def __init__(self, x): self.data x self.next None def detectLoop(head): # 快慢指针初始时都指向头节点 slow head fast head # 循环条件快慢指针均不为空且快指针的下一个节点也不为空 while slow and fast and fast.next: slow slow.next fast fast.next.next # 如果快慢指针指向同一个节点说明检测到环 if slow fast: return True return False if __name__ __main__: head Node(1) head.next Node(3) head.next.next Node(4) head.next.next.next head.next if detectLoop(head): print(true) else: print(false)5. C#using System; class Node { public int data; public Node next; public Node(int x) { this.data x; this.next null; } } class DSA { static bool detectLoop(Node head) { // 快慢指针初始时都指向头节点 Node slow head, fast head; // 循环条件快慢指针均不为空且快指针的下一个节点也不为空 while (slow ! null fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; // 如果快慢指针指向同一个节点说明检测到环 if (slow fast) { return true; } } return false; } static void Main() { Node head new Node(1); head.next new Node(3); head.next.next new Node(4); head.next.next.next head.next; if (detectLoop(head)) Console.WriteLine(true); else Console.WriteLine(false); } }6. JavaScriptclass Node { constructor(x) { this.data x; this.next null; } } function detectLoop(head) { // 快慢指针 // 初始时都指向头节点 let slow head, fast head; // 循环条件快慢指针均不为空且快指针的下一个节点也不为空 while (slow fast fast.next) { slow slow.next; fast fast.next.next; // 如果快慢指针指向同一个节点说明检测到环 if (slow fast) { return true; } } return false; } // Driver Code let head new Node(1); head.next new Node(3); head.next.next new Node(4); head.next.next.next head.next; if (detectLoop(head)) console.log(true); else console.log(false);(三)代码输出和算法复杂度输出true时间复杂度O(n)空间复杂度O(1)