이 튜토리얼에서는 주어진 연결 리스트를 p:q 비율로 나누는 프로그램을 작성할 것입니다.
직관적인 프로그램입니다. 문제를 해결하는 단계를 살펴보겠습니다.
-
연결 목록 노드에 대한 구조체를 만듭니다.
-
더미 데이터로 연결 리스트를 초기화합니다.
-
p:q 비율을 초기화합니다.
-
연결 리스트의 길이를 구하세요.
-
연결 리스트의 길이가 p + q보다 작으면 연결을 p:q 비율로 나눌 수 없습니다.
-
그렇지 않으면 p.까지 연결 목록을 반복합니다.
-
반복 후에 링크를 제거하고 두 번째 연결 목록에 대한 새 헤드를 만듭니다.
-
이제 연결 목록의 두 부분을 인쇄하십시오.
예시
코드를 봅시다.
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *next;
Node(int data) {
this->data = data;
this->next = NULL;
}
};
void printLinkedList(Node* head) {
Node *temp = head;
while (temp) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL" << endl;
}
void splitLinkedList(Node *head, int p, int q) {
int n = 0;
Node *temp = head;
// finding the length of the linked list
while (temp != NULL) {
n += 1;
temp = temp->next;
}
// checking wether we can divide the linked list or not
if (p + q > n) {
cout << "Can't divide Linked list" << endl;
}
else {
temp = head;
while (p > 1) {
temp = temp->next;
p -= 1;
}
// second head node after splitting
Node *head_two = temp->next;
temp->next = NULL;
// printing linked lists
printLinkedList(head);
printLinkedList(head_two);
}
}
int main() {
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
head->next->next->next->next = new Node(5);
head->next->next->next->next->next = new Node(6);
int p = 2, q = 4;
splitLinkedList(head, p, q);
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
1 -> 2 -> NULL 3 -> 4 -> 5 -> 6 -> NULL
결론
튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.