给定一个链表，将链表中的元素两两交换-C++-PHP中文网

给定一个链表，将链表中的元素两两交换

WBOY

发布： 2023-08-26 10:33:10

转载

1481人浏览过

给定一个链表，将链表中的元素两两交换

例如，为了解决需要交换链表中存在的成对节点然后打印它的问题

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中文网其它相关文章！