ADM-201 dump PMP dumps pdf SSCP exam materials CBAP exam sample questions

编程面试题5:如何判断链表是否为循环链表 – 译学馆
未登录,请登录后再发表信息
最新评论 (0)
播放视频

编程面试题5:如何判断链表是否为循环链表

IQ 5: How to detect a cycle in a linked list?

面试问题 5
Interview question 5
今天我为大家准备了一个问题
You know what, I got a question for you guys.
怎样判断一个链表是否包含循环?
How do you determine if a linked list has a loop?
首先要知道这么一个问题
Well, the first thing you have to ask yourself is this.
什么是链表?
What is a linked list?
链表是有序排列元素的集合
Now linked list is an ordered set of elements.
每个元素中存有指向下个元素的连接 所以看起来像这样
Each element contains a link to a successor. So it looks something like this.
图中所示链表包含四个元素 A B C D
Now this link list we have here consists of four elements A B C and D.
我们看下指针的概念
Another thing to take note of is this pointer.
指针是链表中(每个节点)用于存储指向下一个节点的引用
A pointer is something that’s used to point to the next element within a linked list.
链表中每个单独的元素称之为节点
Some other things about linked list is that every element in a linked list is called a node.
节点由两部分构成
And a node consists of two things.
一部分是存储的数据 另一部分是指向链表中下一节点的引用
It consists of data as well as a reference to the next node in the linked list.
所以 如图中所示 每个节点被划分为两个部分
So as you can see here every node is divided up into two parts.
这个节点存有字符值 A
This part of the node consists of a string value of A.
并存有指向下一节点的引用
And this part of the node consists of a reference to the next element,
在这引用也可以叫做 Next()
which can also be referred to as Next(),
指向下一个元素
which is going to point to the next element.
正如我之前所说
And as I said before a pointer is basically something
指针用于指向下一元素
that you use to point to the next element in the list.
链表的最后一个节点
And another thing I want to bring up is that the last node in the list,
不会指向任何元素 所以它的指针为空
is not going to point to another element so that’s why null is placed here.
因为它是最后一个元素 所以它不会指向任何元素
Because it’s not pointing to another element since it is the last element.
那么 链表中的循环是什么呢?
Now what is the loop in a linked list?
如果链表的最后一个元素指向链表中
A loop is pretty much the last element in a linked list
某一个元素 那么这个链表存在循环
that points to an existing element in a linked list.
像这样
So it looks like this.
比如说 我们现在有个链表 包含 ABCDE五个元素
Let’s just say we have a linked list and it contains these values ABCDE.
链表中的最后一个元素
And the last element in the linked list
指向链表中的某个元素
points to an existing element within the linked list.
如果遍历这个链表的话
As you’re making your way through each element in the linked list,
遍历过程是 ABCDE 然后 E 再返回 B
you’re going ABCDE, E makes its way back to B.
B 又开始 沿着 C D E 遍历 循环就产生了
And then B makes its way to C D E and the loop is going to continue.
这就是循环 链表是否包含循环?
So this is what a loop is. Is the list cyclic?
这张幻灯片将像你们展示
What I wanted to do in this slide is to just show you guys
循环链表与非循环链表
that the differences between a cyclic…… a non-cyclic linked lists
之间的差别
and a cyclic linked list.
上面这个链表没有循环
So this linked list here has no loop. There is no cycle.
下面的链表有循环
And this list down here does have a cycle.
这么一比较两者的差别就比较明显了
I just wanted to show the comparison between the two.
那么 怎么判断链表是否是循环链表呢
Now how do you go about determining if a linked list is cyclic.
首先 为了判断链表是否是循环的
First of all, in order to determine if a linked list is cyclic,
我们需要两个指针
the first thing you need is two pointers.
两个指针的起始位置都在链表的头节点上
These two pointers are going to point to the head of the linked list.
两个指针 分为快指针与慢指针
We’re going to have a fast pointer and a slow pointer.
快指针每次移动两个节点
The fast pointer is going to make its way to the list two steps at a time,
慢指针每次移动一个节点
while the slow pointer will make its way to the list one step at a time.
当快指针沿着链表移动的时候
So as the fast pointer is making its way through the list,
就会每隔一个节点进行访问
is going to make its way to the list by skipping every other element.
而慢指针在遍历的时候
While the slow pointer pretty much is going to make its way
每一个元素都要遍历
by hitting every element as it makes its way through the list.
如果想判断链表是否包含循环
Now in order to determine if a list or linked list is cyclic or not,
必须这么做
this is what you would have to do.
如果快指针与慢指针 这两个指针重合了 那么链表中就存在循环
So first of all if the two pointers the fast and the slow pointer meet, then a loop exists.
此时 快指针与慢指针
So that basically means as both the fast and the slow pointer
都应该正在链表中遍历
are making their way through the list.
如果最终两个指针在同一节点相遇
And, if eventually, the two pointers meet up at the same node,
那么循环便存在
then a cycle exists.
但是如果快指针或者慢指针中有一个指向了空
But if either the fast order slow pointer is null,
这就意味着不存在循环
that means that a loop does not exist.
就是说这是个非循环链表 没有循环
Basically mean that the list is acyclic or does not contain a loop.
现在看看实际的遍历过程
Now I wanted to break down the actual traversal explanation.
再来看下这个链表
So let’s just say we have this link list once more.
两个指针 快指针 慢指针
We have a slow pointer we have a fast pointer.
如前面所说 慢指针逐个节点访问
As said the slow pointer is going to make its way once through the list one step at a time.
从 A 开始 到 B C D E B C D E 如此循环
You’re going to start at A make your way to B C D E B C D E and so on.
而快指针一次移动两个节点
Whereas the fast pointer is going to move two steps at a time.
移动过程类似 A C E C E 如此循环
So it’s going to go something like this A C E C E and then continue.
这两行文字 更形象地显示了遍历过程
And this here explains it a bit further.
慢指针遍历过程是 A B C D E B C D
So the slow pointer is going to make its way through the list like this A B C D E B C D.
快指针过程是 A C E C E
And the fast pointer is going to make its way through the list like this A C E C E.
如你所见 这两个指针在同一节点相遇
And if you notice, these two pointers meet up at the same node,
这就意味着这个链表是循环链表 包含循环
which basically means that this list is cyclic, it does contain a loop.
接下来我想复习下
Now what I wanted to do was to go back,
再录个视频解释下
well, actually wanted to create another video that explains,
怎么编写程序检测链表是否是循环的
how you would create an application that detect if a linked list is cyclic or not.
我会用 Java 从头开始实现
Actually want to show you guys how to do that in Java from the ground up.
如果你们有问题直接在视频下面留言就行
So, the meantime, if you have any questions please leave them in the comments below.
如果你们觉得本视频教会了你们些知识 可以点个赞 我们下期视频见
Like the video,if you felt like you’ve learned something here. And see you in the next video.

发表评论

译制信息
视频概述

本视频介绍了检测链表是否为循环链表的解决办法

听录译者

喔喔243

翻译译者

喔喔243

审核员

1024

视频来源

https://www.youtube.com/watch?v=XwtahJ57u7M

相关推荐