給定一個鍊錶，將鍊錶中的元素兩兩交換

例如，為了解決需要交換鍊錶中存在的成對節點然後列印它的問題

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

有兩種方法可以實現時間複雜度為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中文網其他相關文章！