Danh sách được liên kết Chu kỳ II trong C ++

Hãy xem xét chúng ta có một danh sách liên kết và chúng ta phải kiểm tra xem có chu kỳ nào hay không. Để biểu diễn chu trình trong danh sách liên kết đã cho, chúng ta sẽ sử dụng một con trỏ số nguyên được gọi là pos. Vị trí này đại diện cho một vị trí trong danh sách liên kết nơi đuôi được kết nối. Vì vậy, nếu pos là -1, thì không có chu trình nào hiện diện trong danh sách liên kết. Ví dụ, danh sách được liên kết giống như [5, 3, 2, 0, -4, 7] và pos =1. Vì vậy, có một chu kỳ và đuôi được kết nối với nút thứ hai. Hạn chế là chúng tôi không thể sửa đổi danh sách

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• chậm:=đầu và nhanh:=đầu
• trong khi chậm, nhanh và tiếp theo của nhanh đều khả dụng, thì
  • chậm:=tiếp theo của chậm
  • fast:=next of (tiếp theo của fast)
  • nếu chậm =nhanh, thì ngắt
• nếu nhanh không trống hoặc tiếp theo của đầu tiên không trống, thì trả về null
• nếu chậm =nhanh, thì
  • chậm:=head
  • trong khi chậm không giống như nhanh
    • chậm:=tiếp theo của chậm và nhanh:=tiếp theo của nhanh
• trả về chậm

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class ListNode{
   public:
      int val;
      ListNode *next;
      ListNode(int data){
         val = data;
         next = NULL;
      }
};
ListNode *make_list(vector<int> v){
   ListNode *head = new ListNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      ListNode *ptr = head;
      while(ptr->next != NULL){
         ptr = ptr->next;
      }
      ptr->next = new ListNode(v[i]);
   }
   return head;
}
ListNode *get_node(ListNode *head, int pos){
   ListNode *ptr = head;
   if(pos != -1){
      int p = 0;
      while(p < pos){
         ptr = ptr->next;
            p++;
      }
      return ptr;
   }
   return NULL;
}
class Solution {
   public:
   ListNode *detectCycle(ListNode *head) {
      ListNode* slow = head;
      ListNode* fast = head;
      while(slow && fast && fast->next){
         slow = slow->next;
         fast = fast->next->next;
         if(slow == fast)break;
      }
      if(!fast || !fast->next)return NULL;
      if(slow == fast){
         slow = head;
         while(slow!=fast){
            slow = slow->next;
            fast = fast->next;
         }
      }
      return slow;
   }
};
main(){
   Solution ob;
   vector<int> v = {5,3,2,0,-4,7};
   ListNode *head = make_list(v);
   int pos = 1;
   ListNode *lastNode = get_node(head, v.size() - 1);
   lastNode->next = get_node(head, pos);
   cout << "Tail is connected to the node with value:" <<ob.detectCycle(head)->val;
}

Đầu vào

[5,3,2,0,-4,7]
1

Đầu ra

Tail is connected to the node with value:3