C ++は、指定された値の周りにリンクリストを分割し、元の順序を維持します

このチュートリアルでリンクリストが与えられた場合、リストの最初にx未満のすべての数値を保持し、最後に他の数値を保持する必要があります。また、以前と同じ順序を維持する必要があります。たとえば

Input : 1->4->3->2->5->2->3,
x = 3
Output: 1->2->2->3->3->4->5

Input : 1->4->2->10
x = 3
Output: 1->2->4->10

Input : 10->4->20->10->3
x = 3
Output: 3->10->4->20->10

この問題を解決するには、3つのリンクリストを作成する必要があります。 xより小さい数に遭遇したら、それを最初のリストに挿入します。ここで、xに等しい値の場合は、2番目に配置し、より大きい値の場合は、3番目に挿入します。最後に、リストを連結して最終的なリストを印刷します。

解決策を見つけるためのアプローチ

このアプローチでは、3つのリスト、つまり、小さい、等しい、大きいを維持します。今、私たちはそれらの順序を維持し、リストを最終的なリストに連結します。これが私たちの答えです。

例

上記のアプローチのC++コード

#include<bits/stdc++.h>
using namespace std;
struct Node{ // structure for our node
    int data;
    struct Node* next;
};
// A utility function to create a new node
Node *newNode(int data){
    struct Node* new_node = new Node;
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}
struct Node *partition(struct Node *head, int x){
    struct Node *smallhead = NULL, *smalllast = NULL; // we take two pointers for the list                                                     //so that it will help us in concatenation
    struct Node *largelast = NULL, *largehead = NULL;
    struct Node *equalhead = NULL, *equallast = NULL;
    while (head != NULL){ // traversing through the original list
        if (head->data == x){ // for equal to x
            if (equalhead == NULL)
                equalhead = equallast = head;
            else{
                equallast->next = head;
                equallast = equallast->next;
            }
        }
        else if (head->data < x){ // for smaller than x
            if (smallhead == NULL)
                smalllast = smallhead = head;
            else{
               smalllast->next = head;
               smalllast = head;
           }
        }
        else{ // for larger than x
            if (largehead == NULL)
                largelast = largehead = head;
            else{
                largelast->next = head;
                largelast = head;
            }
        }
        head = head->next;
    }
    if (largelast != NULL) // largelast will point to null as it is our last list
        largelast->next = NULL;
   /**********Concatenating the lists**********/
    if (smallhead == NULL){
        if (equalhead == NULL)
           return largehead;
        equallast->next = largehead;
        return equalhead;
    }
    if (equalhead == NULL){
        smalllast->next = largehead;
        return smallhead;
    }
    smalllast->next = equalhead;
    equallast->next = largehead;
    return smallhead;
}
void printList(struct Node *head){ // function for printing our list
    struct Node *temp = head;
    while (temp != NULL){
        printf("%d ", temp->data);
        temp = temp->next;
   }
}
int main(){
    struct Node* head = newNode(10);
    head->next = newNode(4);
    head->next->next = newNode(5);
    head->next->next->next = newNode(30);
    head->next->next->next->next = newNode(2);
    head->next->next->next->next->next = newNode(50);
    int x = 3;
    head = partition(head, x);
    printList(head);
    return 0;
}

出力

2 10 4 5 30

上記のコードの説明

上記のアプローチでは、コンテンツを含む3つのリンクリストを順番に保持します。これらの3つのリンクリストには、xより小さい、等しい、大きい要素が個別に含まれます。これで、タスクが簡略化されました。リストを連結してから、先頭を返す必要があります。

結論

このチュートリアルでは、指定された値を中心にリンクリストを分割し、元の順序を維持することを解決します。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（通常）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。このチュートリアルがお役に立てば幸いです。