例如,为了解决需要交换链表中存在的成对节点然后打印它的问题
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
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 data next;
}
}
int main(){
Node* head = NULL;
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
cout 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 data next;
}
}
int main(){
Node* head = NULL;
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
cout