C++でソートされた循環リンクリストに挿入する

昇順で並べ替えられた循環リンクリストのノードがあるとすると、並べ替えられた循環リストのままになるように、値insertValをリストに挿入する関数を定義する必要があります。

ノードは、リスト内の任意の単一ノードへの参照である可能性があり、必ずしも循環リストの最初の値であるとは限りません。挿入に適した場所が複数ある場合は、新しい値を挿入する場所を選択できます。リストが空の場合は、新しい単一の循環リストを作成し、その単一ノードへの参照を返す必要があります。それ以外の場合は、元の指定されたノードを返す必要があります。

したがって、入力がhead =[3,4,1]、insertVal =2、imageのような場合、出力は[3,4,1,2]、image

これを解決するには、次の手順に従います-

• ヘッドがnullの場合、-

  • head：=valのある新しいノード

  • 頭の次：=頭

• それ以外の場合

  • curr=頭の隣

  • prev=頭

  • temp=valのある新しいノード

  • 完了：=false

  • 無限ループを実行し、-

    を実行します

    • currのval>=valおよびprevのval<=valの場合、-

      • 前：=次の温度

      • temp：=次のcurr

      • 完了：=true

      • ループから出てきます

    • prevのval>currのvalの場合、-

      • prevのval<=valまたはval<=currのvalの場合、-

        • 前：=次の温度

        • temp：=次のcurr

        • 完了：=true

        • ループから出てきます

    • currがheadと同じ場合、-

      • ループから出てきます

    • 前：=curr

    • curr：=currの次

  • doneがfalseの場合、-

    • temp：=次の頭

    • 前：=次の温度

    • 頭：=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