Cho một danh sách liên kết đơn làm đầu vào. Mục tiêu là tách danh sách thành hai danh sách liên kết đơn chứa các nút xen kẽ của danh sách gốc. 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 lấy hai con trỏ N1 và N2, một trỏ đến head của danh sách gốc, cái kia trỏ đến head->next. Di chuyển cả hai con trỏ đến nút next của next và tạo các 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, trỏ next đến các nút xen kẽ để tạo danh sách con như 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, trỏ next đến các nút xen kẽ để tạo danh sách con như trên.
Phương pháp sử dụng trong chương trình dưới đây
Trong phương pháp này, lấy hai con trỏ N1 và N2, một trỏ đến head của danh sách gốc, cái kia trỏ đến head->next. Di chuyển cả hai đến nút next của next và tạo các danh sách con.
Định nghĩa cấu trúc Node với int data và Node* next.
Hàm addtohead(Node** head, int data) thêm nút vào đầu để tạo danh sách liên kết đơn.
Tạo danh sách liên kết đơn bằng hàm trên với head trỏ đến nút đầu.
Hàm display(Node* head) in danh sách liên kết từ nút head.
Khai báo hai con trỏ Node node1 và node2.
Hàm splitList(Node* head, Node** n1, Node** n2) gán n1 = head và n2 = head->next của danh sách gốc.
Bên trong gọi split(*n1, *n2) để tách danh sách gốc thành hai danh sách con.
Hàm split(Node* N1, Node* N2) nhận N1, N2 và tạo hai danh sách con chứa các nút xen kẽ của danh sách gốc.
Nếu cả N1 và N2 đều NULL thì trả về.
Nếu N1->next không NULL thì tmp = N1->next->next, N1->next = tmp.
Nếu N2->next không NULL thì tmp = N2->next->next, N2->next = tmp.
Gọi đệ quy split(N1->next, N2->next) cho lần lặp tiếp theo.
Cuối cùng in các danh sách con bằng display().
Ví dụ mã
#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<<"Danh sách gốc :"<<endl; display(head); splitList(head, &node1, &node2); cout<<endl<<"Danh sách 1: "; display(node1); cout<<endl<<"Danh sách 2: "; display(node2); return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Danh sách gốc : 5 4 10 8 15 12 20 Danh sách 1: 5 10 15 20 Danh sách 2: 4 8 12