Đưa ra một danh sách liên kết Singly làm đầu vào. Mục đích là chia danh sách thành hai danh sách được liên kết đơn lẻ có các nút thay thế của danh sách ban đầu. Nếu danh sách đầu vào có các nút a → b → c → d → e → f thì sau khi tách, hai danh sách con sẽ là a → c → e và b → d → f.
Chúng ta sẽ lấy hai con trỏ N1 và N2, một con trỏ đến phần đầu của danh sách ban đầu và con khác trỏ đến phần đầu → tiếp theo. Bây giờ, hãy di chuyển cả hai con trỏ đến nút tiếp theo và tạo danh sách con.
Ví dụ
Đầu vào - Danh sách:- 1 → 5 → 7 → 12 → 2 → 96 → 33
Đầu ra - Danh sách gốc:1 5 7 12 2 96 33
Danh sách 1:1 7 2 33
Danh sách 2:5 12 96
Giải thích - Bắt đầu từ 1 và 5 và điểm tiếp theo đến các nút thay thế để tạo danh sách con được hiển thị ở trên.
Đầu vào - Danh sách:- 13 → 53 → 90 → 18 → 44 → 11 → 99 → 32
Đầu ra - Danh sách gốc:13 53 90 18 44 11 99 32
Danh sách 1:13 90 44 99
Danh sách 2:53 18 11 32
Giải thích - Bắt đầu từ 13 và 53 và điểm tiếp theo đến các nút thay thế để tạo danh sách con được hiển thị ở trên.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, chúng ta sẽ lấy hai con trỏ N1 và N2, một con trỏ đến phần đầu của danh sách ban đầu và con khác trỏ đến phần đầu → tiếp theo. Bây giờ, hãy di chuyển cả hai con trỏ đến nút tiếp theo và tạo danh sách con.
-
Lấy cấu trúc Node với phần dữ liệu int và Node làm con trỏ tiếp theo.
-
Hàm addtohead (Node ** head, int data) được sử dụng để thêm các nút vào head để tạo một danh sách được liên kết duy nhất.
-
Tạo một danh sách được liên kết đơn lẻ bằng cách sử dụng chức năng trên với head là con trỏ đến nút đầu tiên.
-
Hiển thị hàm (Node * head) được sử dụng để in danh sách liên kết bắt đầu từ nút head.
-
Lấy hai con trỏ Node node1 và node2.
-
Hàm splitList (Node * head, Node ** n1, Node ** n2) nhận con trỏ nút và trỏ n1 tới head và n2 tới head → tiếp theo của chuỗi ban đầu.
-
Bên trong nó gọi split (* n1, * n2) để chia danh sách gốc chứ không phải hai danh sách con
-
Tách hàm (Node * N1, Node * N2) lấy con trỏ N1 và N2 và tạo hai danh sách con chứa các nút xen kẽ của danh sách ban đầu.
-
Nếu cả N1 và N2 đều rỗng thì không trả về kết quả nào.
-
Nếu N1 → next không null thì đặt tmp =N1-> next-> next và N1-> next =tmp;
-
f N2 → tiếp theo không phải là null thì đặt tmp =N2-> tiếp theo-> tiếp theo và N2-> tiếp theo =tmp;
-
Cuộc gọi tách (N1-> tiếp theo, N2-> tiếp theo); cho lần lặp tiếp theo.
-
Ở cuối in danh sách con bằng cách sử dụng display ().
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau
Original List : 5 4 10 8 15 12 20 List 1: 5 10 15 20 List 2: 4 8 12