Chèn vào danh sách được liên kết theo vòng tròn đã sắp xếp trong C ++

Giả sử chúng ta có một nút từ Danh sách liên kết hình tròn được sắp xếp theo thứ tự tăng dần, chúng ta phải xác định một hàm để chèn giá trị insertVal vào danh sách sao cho nó vẫn là một danh sách tròn được sắp xếp.

Nút có thể là một tham chiếu đến bất kỳ nút đơn nào trong danh sách và có thể không nhất thiết phải là giá trị đầu tiên của danh sách vòng tròn. Nếu có nhiều vị trí thích hợp để chèn, chúng ta có thể chọn bất kỳ vị trí nào để chèn giá trị mới. Nếu danh sách trống, thì chúng ta phải tạo một danh sách vòng tròn đơn mới và trả về tham chiếu đến nút đơn đó. Nếu không, chúng ta nên trả về nút đã cho ban đầu.

Vì vậy, nếu đầu vào là head =[3,4,1], insertVal =2, image, thì đầu ra sẽ là [3,4,1,2], image

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

• nếu phần đầu là rỗng, thì -

  • head:=nút mới với val

  • next of head:=head

• Nếu không

  • curr =tiếp theo của đầu

  • trước =đầu

  • temp =nút mới với val

  • xong:=false

  • Thực hiện lặp vô hạn, thực hiện -

    • nếu val trong curr> =val và val của trước <=val, thì -

      • trước:=tiếp theo của tạm thời

      • temp:=next of curr

      • xong:=true

      • Ra khỏi vòng lặp

    • nếu val của trước> val của curr, thì -

      • nếu val của trước <=val hoặc val <=val của curr, thì -

        • trước:=tiếp theo của tạm thời

        • temp:=next of curr

        • xong:=true

        • Ra khỏi vòng lặp

    • nếu curr giống với head, thì -

      • Ra khỏi vòng lặp

    • trước:=curr

    • curr:=next of curr

  • nếu thực hiện là sai, thì -

    • temp:=next of head

    • trước:=tiếp theo của tạm thời

    • head:=temp

• quay trở lại đầu

Ví dụ

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

#include <bits/stdc++.h>
using namespace std;
class Node {
public:
   int val;
   Node* next;
   Node() {}
   Node(int _val) {
      val = _val;
      next = NULL;
   }
   Node(int _val, Node* _next) {
      val = _val;
      next = _next;
   }
};
class Solution {
public:
   Node* insert(Node* head, int val) {
      if(!head){
         head = new Node(val);
         head->next = head;
      }
      else{
         Node* curr = head->next;
         Node* prev = head;
         Node* temp = new Node(val);
         bool done = false;
         while(1){
            if (curr->val >= val && prev->val <= val) {
               prev->next = temp;
               temp->next = curr;
               done = true;
               break;
            }
            if (prev->val > curr->val) {
               if (prev->val <= val || val <= curr->val) {
                  prev->next = temp;
                  temp->next = curr;
                  done = true;
                  break;
               }
            }
            if (curr == head)
               break;
            prev = curr;
            curr = curr->next;
         }
         if(!done){
            temp->next = head;
            prev->next = temp;
            head = temp;
         }
      }
      return head;
   }
};
main(){
   Solution ob;
   Node *head = new Node(3);
   head->next = new Node(4);
   head->next->next = new Node(1, head);
   ob.insert(head, 2);
   Node *temp = head;
   if (head != NULL){
      do{
         cout << temp->val << " ";
         temp = temp->next;
      }
      while (temp != head);
   }
}

Đầu vào

node *head = new Node(3);
head->next = new Node(4);
head->next->next = new Node(1, head);
insertVal = 2

Đầu ra

3 4 1 2