哪建设网站,html5网站基础,直播app开发费用,如何推广引流力扣#xff1a;LCR 022. 环形链表 II 给定一个链表#xff0c;返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环#xff0c;则返回 null。
为了表示给定链表中的环#xff0c;我们使用整数 pos 来表示链…力扣LCR 022. 环形链表 II 给定一个链表返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环则返回 null。
为了表示给定链表中的环我们使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。 如果 pos 是 -1则在该链表中没有环。注意pos 仅仅是用于标识环的情况并不会作为参数传递到函数中。
解法一
快慢指针检测到环后将慢重新指向头在将两个指针一步一步前进二者再次相遇处便是环的入口 原理为
#include iostream
using namespace std;// 定义链表节点结构体
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};// 检测链表中是否有环并返回环的入口节点
ListNode* detectCycle(ListNode* head) {ListNode* slow head;ListNode* fast head;while (fast fast-next) {slow slow-next;fast fast-next-next;if (fast slow) {slow head;while (fast ! slow) {fast fast-next;slow slow-next;}return slow;}}return NULL;
}// 用于创建带有环的链表的辅助函数
ListNode* createCycleListNode(int* values, int size, int cycleIndex) {if (values nullptr || size 0) {return nullptr;}ListNode* head new ListNode(values[0]);ListNode* tail head, *cycleNode nullptr;for (int i 0; i size; i) {ListNode* Node new ListNode(values[i]);tail-next Node;tail Node;if (i cycleIndex) {cycleNode Node;}}if (cycleNode) {tail-next cycleNode;}return head;}// 测试函数
void test(ListNode* head) {ListNode* cycleNode detectCycle(head);if (cycleNode) {std::cout Cycle detected at node with value: cycleNode-val std::endl;}else {std::cout No cycle detected. std::endl;}
}// 主函数
int main() {// 示例创建一个链表其中包含环int values[] { 3, 2, 0, -4 };int cycleIndex 2; // 环的索引从0开始计数这里假设环连接在第三个节点后int size sizeof(values) / sizeof(values[0]);ListNode* head createCycleListNode(values, size, cycleIndex);test(head);// 清理链表delete head-next-next-next;delete head-next-next;delete head-next;delete head;return 0;
}方法二哈希表
哈希表可以记录访问过的节点如果遇到环可以直接将入环的节点返回
#include iostream
#include unordered_set
using namespace std;// 定义链表节点结构体
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};// 检测链表中是否有环并返回环的入口节点ListNode* detectCycle(ListNode* head) {unordered_setListNode* seen;while (head ! nullptr) {if (seen.count(head)) {return head;}seen.insert(head);head head-next;}return nullptr;
}// 用于创建带有环的链表的辅助函数
ListNode* createCycleListNode(int* values, int size, int cycleIndex) {if (values nullptr || size 0) {return nullptr;}ListNode* head new ListNode(values[0]);ListNode* tail head, * cycleNode nullptr;for (int i 0; i size; i) {ListNode* Node new ListNode(values[i]);tail-next Node;tail Node;if (i cycleIndex) {cycleNode Node;}}if (cycleNode) {tail-next cycleNode;}return head;}// 测试函数
void test(ListNode* head) {ListNode* cycleNode detectCycle(head);if (cycleNode) {std::cout Cycle detected at node with value: cycleNode-val std::endl;}else {std::cout No cycle detected. std::endl;}
}// 主函数
int main() {// 示例创建一个链表其中包含环int values[] { 3, 2, 0, -4 };int cycleIndex 2; // 环的索引从0开始计数这里假设环连接在第三个节点后int size sizeof(values) / sizeof(values[0]);ListNode* head createCycleListNode(values, size, cycleIndex);test(head);// 清理链表delete head-next-next-next;delete head-next-next;delete head-next;delete head;return 0;
}
