Memandangkan senarai terpaut, tukar elemen dalam senarai terpaut secara berpasangan-C++-php.cn

Memandangkan senarai terpaut, tukar elemen dalam senarai terpaut secara berpasangan

WBOY

Lepaskan： 2023-08-26 10:33:10

ke hadapan

1328 orang telah melayarinya

Memandangkan senarai terpaut, tukar elemen dalam senarai terpaut secara berpasangan

Sebagai contoh, untuk menyelesaikan masalah perlu menukar pasangan nod yang terdapat dalam senarai terpaut dan kemudian mencetaknya

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

Salin selepas log masuk

Terdapat dua cara untuk mencapai penyelesaian dengan kerumitan masa O(N), di mana N adalah senarai terpaut kami sediakan saiz, jadi sekarang kami akan meneroka kedua-dua kaedah ini

< h2>Kaedah iteratif

Dalam kaedah ini, kami akan mengulangi elemen senarai terpaut dan menukarnya berpasangan demi pasangan sehingga mencapai NULL.

Contoh

#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;
}

Salin selepas log masuk

Output

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

Salin selepas log masuk

Kami akan menggunakan formula yang sama dalam kaedah berikut tetapi kami akan berulang melalui rekursi.

Kaedah Rekursif

Dalam kaedah ini kita melaksanakan logik yang sama melalui rekursi.

Contoh

#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;
}

Salin selepas log masuk

Output

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

Salin selepas log masuk

Penjelasan kod di atas

Dalam kaedah ini, kami melintasi senarai terpaut secara berpasangan. Sekarang apabila kami mencapai pasangan, kami menukar data mereka dan beralih ke pasangan seterusnya dan ini adalah bagaimana program kami meneruskan dalam kedua-dua kaedah.

Kesimpulan

Dalam tutorial ini, kami menyelesaikan pertukaran berpasangan bagi elemen senarai terpaut yang diberikan menggunakan rekursi dan lelaran. Kami juga mempelajari program C++ untuk masalah ini dan kaedah lengkap (generik) untuk menyelesaikannya. Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Kami harap anda mendapati tutorial ini membantu.

Atas ialah kandungan terperinci Memandangkan senarai terpaut, tukar elemen dalam senarai terpaut secara berpasangan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!