数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 给定链表的成对交换元素
要解决一个需要我们交换链表中成对节点并打印的问题，例如
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 和其他语言）中编写相同的程序。我们希望您觉得本教程有所帮助。
更新于: 2021-11-25
322 次浏览
广告