C++에서 정렬된 순환 연결 목록에 삽입

오름차순으로 정렬된 순환 연결 목록의 노드가 있다고 가정하고 정렬된 순환 목록을 유지하도록 insertVal 값을 목록에 삽입하는 함수를 정의해야 합니다.

노드는 목록의 단일 노드에 대한 참조일 수 있으며 순환 목록의 첫 번째 값일 필요는 없습니다. 삽입하기에 적합한 위치가 여러 개인 경우 새 값을 삽입할 위치를 선택할 수 있습니다. 목록이 비어 있으면 새로운 단일 순환 목록을 만들고 해당 단일 노드에 대한 참조를 반환해야 합니다. 그렇지 않으면 원래 주어진 노드를 반환해야 합니다.

따라서 입력이 head =[3,4,1], insertVal =2, image인 경우 출력은 [3,4,1,2], image

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 머리가 null이면 -

  • head :=val이 있는 새 노드

  • 머리 옆 :=머리

• 그렇지 않으면

  • curr =헤드의 다음

  • 이전 =머리

  • temp =val이 있는 새 노드

  • 완료 :=거짓

  • 무한 루프를 수행하고 -

    를 수행합니다.

    • val in curr>=val 및 val of prev <=val이면 -

      • prev :=다음 임시

      • temp :=curr의 다음

      • 완료 :=사실

      • 루프에서 나오세요

    • 이전의 val> curr의 val이면 -

      • 이전의 val <=val 또는 val <=curr의 val이면 -

        • prev :=다음 임시

        • temp :=curr의 다음

        • 완료 :=사실

        • 루프에서 나오세요

    • curr이 head와 같으면 -

      • 루프에서 나오세요

    • 이전 :=현재

    • curr :=curr의 다음

  • 완료가 거짓이면 -

    • temp :=머리 옆

    • prev :=다음 임시

    • 머리 :=온도

• 머리 반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#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