연결된 목록이 주어지면 연결된 목록의 요소를 쌍으로 교환합니다.

예를 들어 연결 목록에 있는 노드 쌍을 교환한 다음 인쇄해야 하는 문제를 해결하려면

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은 연결된 목록은 크기를 제공하므로 이제 이 두 가지 방법을 살펴보겠습니다.

< h2>반복 방법

이 방법에서는 연결된 목록 요소를 반복하고 NULL에 도달할 때까지 쌍으로 교체합니다.

Example

#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;
}

Output

Linked list before
1 2 3 4 5
Linked list after
2 1 4 3 5

다음 방법에서는 동일한 수식을 사용하지만 재귀를 통해 반복합니다.

Recursive Method

이 방법에서는 재귀를 통해 동일한 논리를 구현합니다.

Example

#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;
}

Output

Linked list before
1 2 3 4 5
Linked list after
2 1 4 3 5

위 코드 설명

이 방법에서는 연결된 목록을 쌍으로 순회합니다. 이제 쌍에 도달하면 데이터를 교환하고 다음 쌍으로 이동하며 이것이 두 가지 방법 모두에서 프로그램이 진행되는 방식입니다.

결론

이 튜토리얼에서는 재귀와 반복을 사용하여 주어진 연결 목록 요소의 쌍 교환을 해결했습니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이를 해결하기 위한 완전한 방법(일반)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되었기를 바랍니다.

위 내용은 연결된 목록이 주어지면 연결된 목록의 요소를 쌍으로 교환합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!