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

This article mainly introduces "C++ how to realize the ring in a single-linked list". In daily operation, I believe many people have doubts about how to realize the ring in a single-linked list in C++. Xiaobian consulted all kinds of information and sorted out simple and easy to use operation methods. I hope to help you answer the doubts about "C++ how to realize the ring in a single-linked list"! Next, please follow the small series to learn together!

A loop in a single-stranded list

Example 1:

Input: head = [3,2,0,-4], pos = 1

Output: tail connects to node index 1

Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0

Output: tail connects to node index 0

Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1

Output: no cycle

Explanation: There is no cycle in the linked list.

Follow up:

Can you solve it without using extra space?

The starting point of this search for a loop in a single-linked list is the previous one to determine whether there is an extension of the loop in the single-linked list, which can be referenced in the previous Linked Cycle List. Here is still to set the speed pointer, but this time to record the position of the two pointers meet, when the two pointers meet, let one of the pointers start from the head of the linked list, step by step, step by step like a minion, like the devil's pace. Ha ha, stop, stop... At this time, the position of meeting again is the starting position of the ring in the linked list. Why is this so? Here is the explanation of the enthusiastic netizen "Birds want to fly", because the fast pointer goes 2 every time, and the slow pointer goes 1 every time. The distance of the fast pointer is twice that of the slow pointer. And the fast hand went one more time than the slow hand. So the distance from the head to the beginning of the ring + the beginning of the ring to the point where they meet is equal to the distance of one circle of the ring. Now starting again, the distances from the head running to the beginning of the ring and the point where they meet to the beginning of the ring are also equal, equivalent to both subtracting the distance from the beginning of the ring to the point where they meet. The code is as follows:

class Solution {public: ListNode *detectCycle(ListNode *head) { ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) break; } if (! fast || ! fast->next) return NULL; slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return fast; }}; At this point, the study of "how C++ implements rings in single-linked lists" is over, hoping to solve everyone's doubts. Theory and practice can better match to help you learn, go and try it! If you want to continue learning more relevant knowledge, please continue to pay attention to the website, Xiaobian will continue to strive to bring more practical articles for everyone!

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.