예를 들어 연결 목록에 있는 pairwise 노드를 교환한 다음 인쇄해야 하는 문제를 해결하려면
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
위 코드 설명
이 접근 방식에서는 연결 목록을 쌍으로 탐색합니다. 이제 쌍에 도달하면 데이터를 교환하고 다음 쌍으로 이동합니다. 이것이 두 가지 방법 모두에서 프로그램이 진행되는 방식입니다.
결론
이 튜토리얼에서는 재귀와 반복을 사용하여 주어진 연결 목록의 Pairwise 스왑 요소를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식(Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.