リンクされたリストを指定して、リンクされたリスト内の要素をペアで交換します

たとえば、リンク リストに存在するノードのペアを交換して印刷する必要があるという問題を解決するには、

Input : 1->2->3->4->5->6->NULL

Output : 2->1->4->3->6->5->NULL

Input : 1->2->3->4->5->NULL

Output : 2->1->4->3->5->NULL

Input : 1->NULL

Output : 1->NULL

次の 2 つの方法があります。 O(N ) の時間計算量を達成します。ここで N は、指定したリンク リストのサイズです。そこで、両方のメソッドを検討します

反復メソッド

このメソッドでは、反復処理を行います。リンクされたリスト要素を NULL に達するまでペアで交換します。

例

#include <bits/stdc++.h>
using namespace std;
class Node { // node of our list
public:
    int data;
    Node* next;
};
void swapPairwise(Node* head){
    Node* temp = head;
    while (temp != NULL && temp->next != NULL) { // for pairwise swap we need to have 2 nodes hence we are checking
        swap(temp->data,
            temp->next->data); // swapping the data
        temp = temp->next->next; // going to the next pair
    }
}
void push(Node** head_ref, int new_data){ // function to push our data in list
    Node* new_node = new Node(); // creating new node
    new_node->data = new_data;
    new_node->next = (*head_ref); // head is pushed inwards
    (*head_ref) = new_node; // our new node becomes our head
}
void printList(Node* node){ // utility function to print the given linked list
    while (node != NULL) {
       cout << node->data << " ";
       node = node->next;
    }
}
int main(){
    Node* head = NULL;
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
    cout << "Linked list before\n";
    printList(head);
    swapPairwise(head);
    cout << "\nLinked list after\n";
    printList(head);
    return 0;
}

出力

Linked list before
1 2 3 4 5
Linked list after
2 1 4 3 5

次のメソッドでは同じ式を使用しますが、再帰を繰り返します。

再帰的メソッド

このメソッドでは、再帰を通じて同じロジックを実装します。

例

#include <bits/stdc++.h>
using namespace std;
class Node { // node of our list
public:
    int data;
    Node* next;
};
void swapPairwise(struct Node* head){
    if (head != NULL && head->next != NULL) { // same condition as our iterative
        swap(head->data, head->next->data); // swapping data
        swapPairwise(head->next->next); // moving to the next pair
    }
    return; // else return
}
void push(Node** head_ref, int new_data){ // function to push our data in list
    Node* new_node = new Node(); // creating new node
    new_node->data = new_data;
    new_node->next = (*head_ref); // head is pushed inwards
    (*head_ref) = new_node; // our new node becomes our head
}
void printList(Node* node){ // utility function to print the given linked list
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
}
int main(){
    Node* head = NULL;
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
    cout << "Linked list before\n";
    printList(head);
    swapPairwise(head);
    cout << "\nLinked list after\n";
    printList(head);
    return 0;
}

出力

Linked list before
1 2 3 4 5
Linked list after
2 1 4 3 5

上記のコードの説明

このメソッドでは、リンクされたリストをペアで走査します。ペアに到達したら、データを交換して次のペアに移動します。これが、両方の方法でプログラムがどのように進行するかです。

結論

このチュートリアルでは、再帰と反復を使用して、指定されたリンク リストの要素のペアごとの交換を解決しました。また、この問題に対する C プログラムと、それを解決するための完全な方法 (一般的) も学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。このチュートリアルがお役に立てば幸いです。

以上がリンクされたリストを指定して、リンクされたリスト内の要素をペアで交換しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。