たとえば、リンク リストに存在するノードのペアを交換して印刷する必要があるという問題を解決するには、
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 は、指定したリンク リストのサイズです。そこで、両方のメソッドを検討します
< h2>反復メソッドこのメソッドでは、反復処理を行います。リンクされたリスト要素を 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 サイトの他の関連記事を参照してください。