环形链表(专题，带图示和思路）

2023-10-08 14:04| 来源: 网络整理| 查看: 265

环形链表专题1和II 环形链表思路1代码实现环形链表II思路1代码实现思路2代码实现

环形链表

给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例 1:

输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。

在这里插入图片描述

思路1

初始位置都放在头节点的地方，然后快慢指针一起走，快指针一次走两步（需要注意边界条件），慢指针一次走一步，如果快指针走到nullptr，该链表就不带环；如果快慢指针相遇，该链表就带环。

代码实现 bool hasCycle(ListNode *head) { ListNode *fast = head; ListNode *slow = head; do{ if(fast == NULL || fast->next == NULL){ return false; } else{ slow = slow->next; fast = fast->next->next; } }while(fast != slow); return true; } 环形链表II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1:

输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。

在这里插入图片描述

思路1

使用unordered_set，来保存每一个链表中元素，在保存前先查看set中是否已经存在，若存在说明是环的入口地址，返回该节点即可，否则加入到set里

代码实现 ListNode *detectCycle(ListNode *head) { unordered_set q; ListNode *cur = head; while(cur){ if(q.find(cur) == q.end()){//set中未找到该元素则加入 q.insert(cur); cur = cur->next; } else{//找到说明是环入口地址 return cur; } } return NULL; } 思路2

使用快慢指针，快指针每次移动2步，当有环相遇时，说明快指针走过的路程是慢指针的两倍，假设链表头结点到环入口位置距离为a，环的入口与相遇节点位置距离为b，环的长度为C，我们计算快慢指针所走过的距离：

d(fast) = a + b + C d(slow) = a + b

快指针的速度是慢指针的两倍，相同时间，快指针所走过的路程应该是慢指针所走过路程的两倍，于是：

d(fast) = 2 * d(slow)

所以有：a = C - b 因此在第一次相遇后，将快指针重新从开始，每次一步，下次快慢指针再相遇就是环入口处，对于链表头尾相连情况也是适用的。在这里插入图片描述

代码实现 ListNode *detectCycle(ListNode *head){ ListNode *fast = head; ListNode *slow = head; while(fast != NULL && fast->next != NULL){//找到是否有环 fast = fast->next->next; slow = slow->next; if(fast == slow) //有环，找到环入口 { fast = head; //重新从开始找，每次一步，再相遇就是入口 while(fast != slow){ fast = fast->next; slow = slow->next; } return fast; } } return NULL; }

【本文地址】

公司简介

联系我们