2024-02-21 算法: 测试链表是否有环

---

点击 <C 语言编程核心突破> 快速C语言入门

---

---

前言

要解决问题: 一道简单的算法题, 测试链表是否含有环.

想到的思路: 哈希表, 将链表指针强制转换为整型, 利用求余法建立哈希函数. 太复杂, 内存效率不高, 经题解发现可用双指针, 即快慢指针法.

其它的补充: 简单算法题, 未看题解没做出来, 脑袋跟不上了.

---

一、双指针 ( 快慢指针 )

快慢指针, 就是用两个链表节点指针, 快指针每循环一次前进一个, 慢指针每循环两次前进一个, 如果有环, 快指针会套圈慢指针, 此时两指针相等, 如果没有环, 快指针会遍历完成, 并结束.

二、代码

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct ListNode
{int val;struct ListNode *next;
} ListNode;bool hasCycle(ListNode *head)
{if (!head){return false;}ListNode *slow = head;int num = 0;head = head->next;num++;while (head){if (head == slow){return true;}head = head->next;num++;if (num % 2 == 0){slow = slow->next;}}return false;
}

---

总结

只要有思路, 其实很简单, 没有思路, 则比较难.

---

点击 <C 语言编程核心突破> 快速C语言入门

---