กำหนดรายการเชื่อมโยงแบบเดี่ยวเป็นอินพุต เป้าหมายคือการแบ่งรายการออกเป็นสองรายการที่เชื่อมโยงโดยลำพังซึ่งมีโหนดสำรองของรายการดั้งเดิม หากรายการอินพุตมีโหนด 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 และโหนดเป็นตัวชี้ถัดไป
-
ฟังก์ชัน addtohead(โหนด** head, int data) ใช้เพื่อเพิ่มโหนดในส่วนหัวเพื่อสร้างรายการที่เชื่อมโยงโดยลำพัง
-
สร้างรายการที่เชื่อมโยงโดยลำพังโดยใช้ฟังก์ชันข้างต้นโดยมีส่วนหัวเป็นตัวชี้ไปยังโหนดแรก
-
การแสดงฟังก์ชัน (หัวโหนด*) ใช้เพื่อพิมพ์รายการที่เชื่อมโยงโดยเริ่มจากโหนดหลัก
-
ใช้ตัวชี้โหนดสองตัว node1 และ node2
-
ฟังก์ชัน splitList(หัวโหนด*, โหนด** n1, โหนด** n2) นำพอยน์เตอร์ของโหนดและชี้ n1 ไปที่ส่วนหัว และ n2 ไปยังส่วนหัว → ถัดจากสตริงเดิม
-
ข้างในนั้นเรียก split(*n1, *n2) เพื่อแยกรายการดั้งเดิมออกเป็นสองรายการย่อย
-
การแยกฟังก์ชัน (โหนด* N1, โหนด* N2) รับตัวชี้ N1 และ N2 และสร้างรายการย่อยสองรายการที่มีโหนดสลับกันของรายการดั้งเดิม
-
หากทั้ง N1 และ N2 เป็นโมฆะ ก็จะไม่ส่งคืนสิ่งใด
-
ถ้า N1→ next ไม่เป็นค่าว่าง ให้ตั้งค่า tmp=N1->next->next และ N1->next =tmp;
-
f N2→ next ไม่เป็นค่าว่าง จากนั้นให้ตั้งค่า tmp=N2->next->next และ N2->next =tmp;
-
การแยกการโทร (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
