Shulou(Shulou.com)05/31 Report--

Most people don't understand the knowledge points of this article "how to realize one-way circular linked list in C language data structure", so Xiaobian summarizes the following contents for everyone. The contents are detailed, the steps are clear, and they have certain reference value. I hope everyone can gain something after reading this article. Let's take a look at this article "how to realize one-way circular linked list in C language data structure".

1. Example introduction

Links to:

circular linked list

Title:

2. What is a linked list

Each node of a normal single-linked list is linked sequentially, and the last node points to NULL, as follows:

The last node of the linked list no longer points to NULL, but points to any node in front of it, forming a linked list and looping all the time. As follows:

3. Solution to the problem

We can represent the above abstract point of the picture by a straight line before entering the ring and a circle after entering the ring, thus indicating the cycle. This problem needs to use the idea of finding the middle node and finding the speed pointer of the last kth node that we explained before. Define two pointers slow and fast, both pointing to a starting position. Let slow take one step at a time and fast take two steps at a time.

When slow is halfway through the line, fast is at the entry point of the loop.

Suppose slow just reaches the entry point of the ring, fast goes to the following position, at which time fast starts chasing mode

fast begins to catch up with slow, assuming fast begins to catch up with slow at

The code is as follows:

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;}

From the perspective of disintegration, this problem is not complicated, only need to use the idea of fast and slow pointer can be solved, only this problem can lead to a number of problems worthy of our discussion, in order to deepen our understanding of the circular linked list, the following three major expansion problems:

4. Expansion problems

(1) Slow one step at a time, fast two steps at a time, can you catch up?

Answer: Certainly.

Proof:

When slow gets to the middle, fast must be in the ring, and fast starts chasing. Let's assume that after slow enters the loop, the distance between slow and fast is N. In this case, slow takes 1 step and fast takes 2 steps, and their distance decreases by 1 to N − 1. And so on, each time the pursuit, the distance reduced by 1, when the distance reduced to 0 when they caught up. In conclusion, it must be able to catch up.

(2) Slow one step at a time, fast three steps at a time, can you catch up? Fast 4 steps at a time? N steps?

Answer: Not necessarily.

Proof:

Let's start with slow taking one step at a time and fast taking three steps at a time. Suppose slow takes one step, fast takes three steps and enters the ring, and when slow enters the ring, fast may have already gone one turn, depending on the size of the ring, and the distance between slow and fast is N. And suppose the length of the ring is C.

Slow takes 1 step at a time, fast takes 3 steps at a time, and the distance becomes N-2. Each time fast and slow are taken, the distance is shortened by 2. At this point it is not difficult to find, need to classify the discussion, when N is even, just can catch up, when N is odd, catch up to the final distance of-1, at this time we have to catch up again, meaning that the distance between slow and fast becomes C-1.

Continue to pursue, according to the previous analysis, if C-1 is even, then you can catch up. If C-1 is odd, then it will never catch up, and it will continue to catch up wirelessly, but it will not catch up. Their difference N is determined by the length before entering the ring and the length of the ring, and these two are random, so the value of N is uncertain, odd or even, and as we have just discussed, odd numbers will never return.

The same is true for fast walking 4 steps at a time. The same is not necessarily true, but at this time, every time you walk, the distance is shortened by 3. When N is a multiple of 3, you can catch up. When it is not a multiple of 3, you will continue to discuss it. Interested children can continue to study it. The idea is the same as fast walking three steps at a time. I won't repeat it here.

(3) Where is the entry point of the linked list ring?

When we figure out how far slow and fast travel, the entry point becomes clear.

Law 1:

Slow takes one step at a time, fast takes two steps at a time, so fast takes twice as long as slow.

Before explaining in detail, first of all, we must make it clear that there is no such thing as slow pointer walking a circle inside, fast pointer fast has not caught up with slow, because fast takes 2 steps each time, slow takes 1 step each time, the distance between them is reduced by 1 each time, so it will only get closer and closer until it catches up. At best, it's a lap faster, but it's never exactly a full lap. So it's easy to deduce how much slow and fast have gone.

Assumptions:

[Chain Head- - -Entry Point]: L

[Entry Point- - -Meeting Point]: X

[Length of Ring]: C

Slow distance: L + X

Fast distance: L + N*C + X

Explanation:

Because it has been mentioned earlier that slow will not walk a circle and not be caught, it is easy to deduce that the distance of slow is L+X.

The fast pointer takes two steps at a time, and it is likely that the ring is too small to cause the fast pointer to go several times before the slow pointer enters the entry point. In short, three sentences:

L is very small, C is very large, slow before entering the ring, fast may be inside the ring, and it has not finished a circle.

L is very big, C is very small, slow before entering the ring, fast has walked many circles inside

But after slow enters the ring, fast must catch up to slow within a circle, and their distance is at most C-1.

According to what was said at the beginning, fast travels twice as far as slow travels, and the following formula can be listed:

2*(L+X) = L + N*C + X

Simplified: L+X = N*C or L = N*C - X or L = (N-1)*C + (C-X) or L + X = N*C

This formula proves that one pointer goes from meet and one pointer goes from head, and they meet at the entry point!

Since the formula (N − 1)*C indicates that after N − 1 turns from the meeting point, they return to the meeting point, and at this time, they return to the entry point by a distance of C − X, we know from above that this formula does bring them back to the entry point.

Use a practical question to specify the location of the entrance point: Link to:

Circular List 2.0--> Find Entry Point

Title:

The code is as follows:

struct ListNode* detectCycle(struct ListNode* head) { struct ListNode* slow = head; struct ListNode* fast = head; while (fast && fast->next) { //determine whether it is a linked list slow = slow->next; fast = fast->next->next; if (slow == fast) { struct ListNode* meet = slow; while (meet != head) { //Find the meeting point meet = meet->next; head = head->next; } return meet; } } return NULL;}

There is another way to find the meeting point:

After finding the meeting point, let meet be the tail and let the next point be the head of the new linked list.

The above is about the content of this article on "how to realize one-way circular list in C language data structure". I believe everyone has a certain understanding. I hope the content shared by Xiaobian will be helpful to everyone. If you want to know more relevant knowledge content, please pay attention to the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.