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.
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,
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.