C++ 成对交换给定链表的元素
c++server side programmingprogramming
为了解决需要交换链表中的成对节点然后打印的问题，例如
输入:1->2->3->4->5->6->NULL 输出:2->1->4->3->6->5->NULL 输入:1->2->3->4->5->NULL 输出:2->1->4->3->5->NULL 输入:1->NULL 输出:1->NULL
有两个两种方法都可以使解决方案的时间复杂度为 O(N)，其中 N 是我们提供的链表的大小，所以现在我们将探索这两种方法
迭代方法
我们将在这种方法中迭代链表元素，并成对交换它们，直到它们达到 NULL。
示例
#include <bits/stdc++.h>
using namespace std;
class Node { // 我们列表的节点
public:
int data;
Node* next;
};
void swapPairwise(Node* head){
Node* temp = head;
while (temp != NULL && temp->next != NULL) { // 对于成对交换，我们需要有 2 个节点，因此我们正在检查
swap(temp->data,
temp->next->data); // 交换数据
temp = temp->next->next; // 转到下一对
}
}
void push(Node** head_ref, int new_data){ // 将数据推送到列表中的函数
Node* new_node = new Node(); // 创建新节点
new_node->data = new_data;
new_node->next = (*head_ref); // head 被向内推
(*head_ref) = new_node; // 我们的新节点成为我们的 head
}
void printList(Node* node){// 用于打印给定链接列表的实用函数
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 { // 我们列表的节点
public:
int data;
Node* next;
};
void swapPairwise(struct Node* head){
if (head != NULL && head->next != NULL) { // 与我们的迭代条件相同
swap(head->data, head->next->data); // 交换数据
swapPairwise(head->next->next); // 移动到下一对
}
return; // 否则返回
}
void push(Node** head_ref, int new_data){ // 将数据推送到列表中的函数
Node* new_node = new Node(); // 创建新节点
new_node->data = new_data;
new_node->next = (*head_ref); // 头部被向内推
(*head_ref) = new_node; // 我们的新节点成为我们的头节点
}
void printList(Node* node){// 用于打印给定链接列表的实用函数
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 和其他语言。我们希望您觉得本教程有用。
