如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数来表示链表尾连接到链表中的位置(索引从 0 开始)。
先定义一个节点:
struct ListNode {
int val;
struct ListNode *next;
};
寻找环形链表入口点的第一步,要先判断该链表是否为环形链表,环形链表的尾指针指向的位置是不确定的,可能指向首元素,这样的形成的链表环就是很大,也可能指向链表中间的随机元素,也可能指向尾节点本身,新形成的环很小。
带有环的链表如图所示:
判断是否为环形链表,我们采用双指针的方法,即快慢指针,慢指针一次移动一个节点,快指针一次移动两个节点。如果该链表带环,快指针和慢指针就会在环里相遇,否则快指针就会走到尾部。判断是否带环的代码如下:
如果链表中存在环,则返回 true ,否则返回 false
bool hasCycle(struct ListNode *head)
{
struct ListNode* slow=head;
struct ListNode* fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
return true;
}
return false;
}
对于以上代码我们提出两个问题;
答:他们一定会在环里相遇,不会追不上。
假设slow进环的时候,slow和fast的距离是N,紧接着在追击的过程中,fast往前走2步,slow往前走1步。他们每走一次,他们之间的距离聚就会缩小1.
N , N-1 , N-2…2 , 1 , 0
当N为0时slow和fast相遇。
答:假设slow进环的是时候,fast和slow的距离是N,假设slow走1步,fast走3步。由(1)可知,在追击的过程中,fast往前走3步,slow往前走1步,他们每次之间的距离缩短2。
如果N是偶数:N , N-2 , N-4…2 , 0;则可以相遇。
如果N是奇数:N , N-2 , N-4…1 , -1;此时差距为C-1(C为环的长度),如果C-1恰好也是奇数,那么就永远也追不上。
***总结:如果slow进环时,slow和fast的差距N是奇数,且环的长度是偶数(C-1为奇数),那么他们两在环里面就会一直打圈,永远追不上。
假设起点到入口点的距离是L,
假设相遇点到入口点的距离是X,
假设环的大小是C
所以慢指针走的路程:L+X
快指针走的路程:L+NC+X(N为快指针在相遇之前走了多少圈,如果环很大,可能再相遇之前一圈没有走完,如果环很小,可能在相遇之前快指针已经在环里走过很多圈)
由以上可以推出:L=NC-X
***总结:一个指针从相遇点走,一个指针从起点走,他们会在入口点相遇。
找到环形链表的入口点的代码如下:
struct ListNode* detectCycle(struct ListNode* head)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (fast == slow)
{
struct ListNode* meet = fast;
while (meet != head)
{
meet = meet->next;
head = head->next;
}
return meet;
}
}
return NULL;
}
实现如上代码,给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
方法如下: response.cookies(cookiesname)[(key)|.attribute]=value 解释如下:...
1.现在复习的感觉就是:马上要有一大波僵尸涌过来,但老子连向日葵都还没种! 2...
当我们想要持久化地存储数据时,使用关系型数据库往往都是最稳妥的选择,这不仅...
欢迎访问我的GitHub 这里分类和汇总了欣宸的全部原创(含配套源码) https://githu...
这道题要求我们判断输出的一个字符串中的括号是否符合运算规律。可以运用栈的思...
必须以html格式返回json数据 即response.setContentType(text/html; charset=utf...
IT之家12月23日消息 外媒 Windows Latest 报道,随着 Windows 10 版本 2004 的发...
文档模式主要有以下两个作用: 1、告诉浏览器使用什么样的html或xhtml规范来解析...
git工作区,暂存区,版本库之间的关系: 我们建立的项目文件夹就是工作区,在初...
项目场景: 数据可视化大屏开发的过程中,需要实现一种滚动数字的效果,在使用vu...