입력으로 단일 연결 목록이 제공됩니다. 목표는 목록을 원래 목록의 대체 노드가 있는 두 개의 단일 연결 목록으로 분할하는 것입니다. 입력 목록에 노드 a → b → c → d → e → f가 있는 경우 분할 후 두 개의 하위 목록은 a → c → e 및 b → d → f가 됩니다.
우리는 두 개의 포인터 N1과 N2를 취할 것입니다. 하나는 원래 목록의 머리를 가리키고 다른 하나는 머리 → 다음을 가리킵니다. 이제 두 포인터를 다음 노드로 이동하고 하위 목록을 만듭니다.
예시
입력 − 목록 :- 1 → 5 → 7 → 12 → 2 → 96 → 33
출력 − 원본 목록:1 5 7 12 2 96 33
목록 1:1 7 2 33
목록 2:5 12 96
설명 − 1과 5에서 시작하고 다음은 대체 노드를 가리켜 위에 표시된 하위 목록을 만듭니다.
입력 − 목록 :- 13 → 53 → 90 → 18 → 44 → 11 → 99 → 32
출력 − 원본 목록:13 53 90 18 44 11 99 32
목록 1:13 90 44 99
목록 2:53 18 11 32
설명 − 13과 53에서 시작하고 다음은 위에 표시된 하위 목록을 만들기 위해 대체 노드를 가리킵니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
이 접근법에서 우리는 두 개의 포인터 N1과 N2를 취할 것입니다. 하나는 원래 목록의 머리를 가리키고 다른 하나는 머리→다음을 가리킵니다. 이제 두 포인터를 다음 노드로 이동하고 하위 목록을 만듭니다.
-
int 데이터 부분이 있는 Node 구조와 다음 포인터로 Node를 사용합니다.
-
addtohead(Node** head, int data) 함수는 단일 연결 리스트를 생성하기 위해 헤드에 노드를 추가하는 데 사용됩니다.
-
첫 번째 노드에 대한 포인터로 head를 사용하여 위의 함수를 사용하여 단일 연결 목록을 만듭니다.
-
기능 display(Node* head)는 헤드 노드부터 연결 리스트를 출력하는데 사용됩니다.
-
두 개의 노드 포인터 node1과 node2를 가져옵니다.
-
함수 splitList(Node* head, Node** n1, Node** n2)는 노드 포인터를 사용하여 n1을 헤드로, n2를 헤드 → 원본 문자열의 다음으로 가리킵니다.
-
내부에서 split(*n1, *n2)을 호출하여 원래 목록을 두 개의 하위 목록으로 분할합니다.
-
split(Node* N1, Node* N2) 함수는 N1 및 N2 포인터를 사용하고 원래 목록의 교대 노드를 포함하는 두 개의 하위 목록을 만듭니다.
-
N1과 N2가 모두 null이면 아무 것도 반환하지 않습니다.
-
N1→ next가 null이 아닌 경우 tmp=N1->next->next 및 N1->next =tmp;
로 설정합니다. -
f N2→ next는 null이 아닌 경우 tmp=N2->next->next 및 N2->next =tmp를 설정합니다.
-
호출 split(N1->다음, N2->다음); 다음 반복을 위해.
-
마지막에 display()를 사용하여 하위 목록을 인쇄합니다.
예시
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void addtohead(Node** head, int data){
Node* nodex = new Node;
nodex->data = data;
nodex->next = (*head);
(*head) = nodex;
}
void split(Node* N1, Node* N2){
Node *tmp;
if (N1 == NULL || N2 == NULL){
return;
}
if (N1->next != NULL){
tmp=N1->next->next;
N1->next = tmp;
}
if (N2->next != NULL){
tmp=N2->next->next;
N2->next = tmp;
}
split(N1->next, N2->next);
}
void splitList(Node* head, Node** n1, Node** n2){
*n1 = head;
*n2 = head->next;
split(*n1, *n2);
}
void display(Node* head){
Node* curr = head;
if (curr != NULL){
cout<<curr->data<<" ";
display(curr->next);
}
}
int main(){
Node* head = NULL;
Node *node1 = NULL, *node2 = NULL;
addtohead(&head, 20);
addtohead(&head, 12);
addtohead(&head, 15);
addtohead(&head, 8);
addtohead(&head, 10);
addtohead(&head, 4);
addtohead(&head, 5);
cout<<"Original List :"<<endl;
display(head);
splitList(head, &node1, &node2);
cout<<endl<<"List 1: ";
display(node1);
cout<<endl<<"List 2: ";
display(node2);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Original List : 5 4 10 8 15 12 20 List 1: 5 10 15 20 List 2: 4 8 12