단일 연결 목록은 두 부분을 포함하는 선형 데이터 구조입니다. 하나는 데이터이고 다른 하나는 목록의 다음 요소에 대한 포인터입니다.
홀수 및 짝수 단일 연결 목록 대체 데이터가 짝수인 노드와 데이터가 홀수인 노드가 있는 연결 리스트입니다.
이 문제에서는 대체 홀수 및 짝수 단일 연결 목록을 정의하는 두 가지 방법 중 하나로 미리 정의된 단일 연결 목록의 요소를 재배열해야 합니다.
두 가지 방법은 - 연결 목록의 첫 번째 요소가 짝수이면 다음 요소는 홀수여야 하고 다음 요소는 짝수여야 합니다. 즉, 세 번째 요소는 다시 짝수입니다. 다른 유형은 첫 번째 요소가 홀수이면 다음 요소는 짝수여야 하고 다음 요소는 홀수여야 합니다. 즉, 세 번째 요소는 홀수입니다.
개념을 더 잘 이해할 수 있도록 예시를 살펴보겠습니다.
연결 리스트가 − 45> 21> 2> 213> 3> 34> 78>12라고 가정합니다.
결과 연결 목록은 45> 2>21>34> 213> 78> 3>12
가 됩니다.이제 이 연결 목록에는 짝수와 홀수 요소가 있으므로 이를 재정렬하기 위해 2, 34, 78,12를 연속 짝수 위치에 배치하고 45, 21, 213, 3을 연속 홀수 위치에 배치합니다.
이제 문제를 이해했으므로 이에 대한 해결책을 찾기 위해 노력할 것입니다. 이러한 유형의 문제를 해결하는 방법에는 여러 가지가 있을 수 있습니다. 간단한 방법은 스택을 사용하는 것입니다. 우리는 두 개의 스택을 만들 것입니다. 하나는 짝수 값이고 다른 하나는 홀수 값입니다. 순서가 잘못된 노드, 즉 홀수 위치에 있는 짝수 노드를 만나면 주소를 짝수 스택으로 푸시하고 홀수 스택에 대해서도 마찬가지로 푸시합니다. 그리고 탐색이 끝나면 스택에서 노드를 꺼냅니다.
이 논리를 기반으로 우리는 알고리즘을 만들 것입니다 -
알고리즘
Step 1 : Create stacks for holding out of order even and odd node of the linked list. Step 2 : Traverse the linked list and follow : Step 2.1 : if odd node is out of order i.e. at odd position, push it to odd stack. Step 2.2 : If even node is out of order i.e. at even position, push it to even stack. Step 3 : Push elements from the stack in alternate order. When the stack is empty, the result is the required linked list. Step 4: Print the elements of the linked list.
예시
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void printList(struct Node* node) ;
Node* newNode(int key){
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
Node* insertBeg(Node* head, int val){
Node* temp = newNode(val);
temp->next = head;
head = temp;
return head;
}
void OddEvenList(Node* head) ;
int main(){
Node* head = newNode(45);
head = insertBeg(head, 21);
head = insertBeg(head, 2);
head = insertBeg(head, 213);
head = insertBeg(head, 3);
head = insertBeg(head, 34);
head = insertBeg(head, 78);
head = insertBeg(head, 12);
cout << "Linked List:" << endl;
printList(head);
OddEvenList(head);
cout << "Linked List after "
<< "Rearranging:" << endl;
printList(head);
return 0;
}
void printList(struct Node* node){
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
void OddEvenList(Node* head){
stack<Node*> odd;
stack<Node*> even;
int i = 1;
while (head != nullptr) {
if (head->data % 2 != 0 && i % 2 == 0) {
odd.push(head);
}
else if (head->data % 2 == 0 && i % 2 != 0) {
even.push(head);
}
head = head->next;
i++;
}
while (!odd.empty() && !even.empty()) {
swap(odd.top()->data, even.top()->data);
odd.pop();
even.pop();
}
} 출력
Linked List: 12 78 34 3 213 2 21 45 Linked List after Rearranging: 3 78 45 12 213 2 21 34