• #### 科普

SCIENCE

#### 英语

ENGLISH

#### 科技

TECHNOLOGY

MOVIE

FOOD

#### 励志

INSPIRATIONS

#### 社会

SOCIETY

TRAVEL

#### 动物

ANIMALS

KIDS

#### 卡通

CARTOON

#### 计算机

COMPUTER

#### 心理

PSYCHOLOGY

#### 教育

EDUCATION

#### 手工

HANDCRAFTS

#### 趣闻

MYSTERIES

CAREER

GEEKS

#### 时尚

FASHION

• 精品课
• 公开课
• 欢迎下载我们在各应用市场备受好评的APP

点击下载Android最新版本

点击下载iOS最新版本

扫码下载译学馆APP

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

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

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.

Now linked list is an ordered set of elements.

Each element contains a link to a successor. So it looks something like this.

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.

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,

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

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.

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.

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.

So the slow pointer is going to make its way through the list like this A B C D E B C D.

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.

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.

1024