แทรกลงในรายการเชื่อมโยงที่เรียงลำดับแบบวงกลมใน C++

สมมติว่าเรามีโหนดจาก Circular Linked List ซึ่งถูกจัดเรียงตามลำดับที่เพิ่มขึ้น เราต้องกำหนดฟังก์ชันเพื่อแทรกค่า insertVal ลงในรายการเพื่อให้ยังคงเป็นรายการแบบวงกลม

โหนดสามารถอ้างอิงถึงโหนดเดียวในรายการ และอาจไม่จำเป็นต้องเป็นค่าแรกของรายการแบบวงกลม หากมีหลายตำแหน่งที่เหมาะสมในการแทรก เราสามารถเลือกตำแหน่งใดๆ เพื่อใส่ค่าใหม่ได้ หากรายการว่างเปล่า เราต้องสร้างรายการวงกลมเดี่ยวใหม่และส่งคืนการอ้างอิงไปยังโหนดเดียวนั้น มิฉะนั้น เราควรคืนค่าโหนดที่กำหนดเดิม

ดังนั้น หากอินพุตเป็นเหมือน head =[3,4,1], insertVal =2, รูปภาพ ผลลัพธ์จะเป็น [3,4,1,2], รูปภาพ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ้า head เป็นโมฆะ −

  • head :=โหนดใหม่พร้อม val

  • ข้างหัว :=หัว

• มิฉะนั้น

  • curr =ถัดไปของหัว

  • ก่อนหน้า =หัว

  • temp =โหนดใหม่พร้อม val

  • เสร็จสิ้น :=เท็จ

  • ทำวนซ้ำไม่สิ้นสุด ทำ -

    • ถ้า val ในสกุลเงิน>=val และ val ของก่อนหน้า <=val แล้ว −

      • ก่อนหน้า :=ถัดไปของอุณหภูมิ

      • temp :=ถัดไปของ curr

      • เสร็จสิ้น :=จริง

      • ออกจากวง

    • ถ้า val ของ prev> val ของ curr แล้ว −

      • ถ้า val ของ prev <=val หรือ val <=val ของ curr แล้ว −

        • ก่อนหน้า :=ถัดไปของอุณหภูมิ

        • temp :=ถัดไปของ curr

        • เสร็จสิ้น :=จริง

        • ออกจากวง

    • ถ้าสกุลเงินเท่ากับหัว −

      • ออกจากวง

    • ก่อนหน้า :=สกุลเงิน

    • curr :=ถัดไปของสกุลเงิน

  • ถ้าทำเป็นเท็จ −

    • temp :=ถัดไปของหัว

    • ก่อนหน้า :=ถัดไปของอุณหภูมิ

    • หัว :=อุณหภูมิ

• กลับหัว

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

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

ผลลัพธ์

3 4 1 2