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

This article mainly introduces the relevant knowledge of "how to realize C++ circular linked list". The editor shows you the operation process through an actual case, and the operation method is simple, fast and practical. I hope this "how to achieve C++ circular linked list" article can help you solve the problem.

Algorithm:

The core point of this kind of problem is how to judge whether it is a circular linked list, and the core idea is: if two people run on the ring, sooner or later they will catch up with the slow ones.

Is a typical use of fast and slow pointers.

Topic 1: circular linked list

Code implementation:

/ * Definition for singly-linked list. * type ListNode struct {* Val int * Next * ListNode *} * / func hasCycle (head * ListNode) bool {if head = = nil | | head.Next = = nil {return false} slow: = head / / slow pointer one step at a time fast: = head.Next / / two steps at a time with fast pointer for slow! = fast {if slow = nil | fast = = nil {return false } slow = slow.Next fast = fast.Next if fast! = nil {fast = fast.Next}} return true}

Topic 2: loop detection

Code implementation:

/ / algorithm: this problem is mainly divided into two steps. The first step is to find the intersection position in the circular linked list. / / the second step is to let the slow pointer point to the head of the linked list, the position of the fast pointer remains the same, / / then the fast and slow pointer takes one step at a time, and the entrance position of the circular linked list is when we meet again. / * Definition for singly-linked list. * type ListNode struct {* Val int * Next * ListNode *} * / func detectCycle (head * ListNode) * ListNode {s, f: = head Head for f! = nil & & f.Next! = nil {s = s.Next f = f.Next.Next if f = = s {/ / determine whether there is a ring break}} if f = = nil | | f.Next = = nil {/ / the fast pointer is in the ring at this time In theory, neither of these should be empty. / / if there is only one node, f.Next = = nil return nil}

S = head for s! = f {s = s.Next f = f.Next} return s} that's all for "how to implement C++ 's circular linked list". Thank you for reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

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.