รายการที่เชื่อมโยงเป็นโครงสร้างข้อมูลเชิงเส้นซึ่งแต่ละโหนดมีสองบล็อก โดยที่หนึ่งบล็อกมีค่าหรือข้อมูลของโหนด และอีกบล็อกหนึ่งมีที่อยู่ของฟิลด์ถัดไป
สมมติว่าเรามีรายการที่เชื่อมโยงซึ่งแต่ละโหนดมีข้อมูลและตัวชี้ซึ่งชี้ไปยังโหนดถัดไปของรายการที่เชื่อมโยง งานคือการแยกรายการเชื่อมโยงที่กำหนด การแยกรายการที่เชื่อมโยงหมายความว่าเราต้องแยกโหนดที่มีดัชนีคี่และโหนดดัชนีในรายการ
แนวทางในการแก้ปัญหานี้
ในการแยกรายการเชื่อมโยงที่กำหนด เราจะแนะนำตัวชี้สามตัวสำหรับดัชนีคี่ ดัชนีคู่ และค่าที่ดัชนีคู่ ตามลำดับ หลังจากนั้น เราจะวนซ้ำบนรายการที่เชื่อมโยงทั้งหมดและเริ่มต้นตัวชี้ด้วยค่าบางอย่าง
ในรายการที่เชื่อมโยง การสร้างดัชนีเริ่มต้นจาก '1' ดังนั้นสำหรับสตริงใด ๆ โหนดแรกของรายการจะถือว่าเป็นโหนดที่จัดทำดัชนีคี่เสมอ อย่างไรก็ตาม โหนดถัดไปจะถือเป็นโหนดที่จัดทำดัชนีแบบคู่
- นำรายการที่เชื่อมโยงพร้อมข้อมูลและตัวชี้ไปยังโหนดถัดไป
- ฟังก์ชัน segregateList(listnode *head) นำพอยน์เตอร์ไปที่ head node และส่งคืนรายการที่เชื่อมโยงที่แยกออกเป็นเอาต์พุต
- เริ่มต้นตัวชี้สามตัว oddIndex, evenIndex และ evenHead ซึ่งกำลังชี้ไปที่ส่วนหัวของรายการ
- วนซ้ำในรายการที่เชื่อมโยงทั้งหมดและเริ่มต้นตัวชี้ถัดไปของ oddIndex ด้วยตัวชี้ถัดไปของevenIndex
- ตอนนี้ วนซ้ำทั่วทั้งรายการและเริ่มต้นตัวชี้ถัดไปของevenIndexด้วยตัวชี้ถัดไปของ oddIndex
- ส่งคืนตัวชี้ส่วนหัว
ตัวอย่าง
#include <iostream>
using namespace std;
class node {
public:
int data;
node * next;
node(int d) {
data = d;
next = NULL;
}
};
node * segregateList(node * head) {
if (head == NULL) {
return NULL;
}
node * oddIndex = head;
node * evenIndex = head -> next;
node * evenHead = evenIndex;
while (evenIndex != NULL and evenIndex -> next != NULL) {
oddIndex -> next = evenIndex -> next;
oddIndex = oddIndex -> next;
evenIndex -> next = oddIndex -> next;
evenIndex = evenIndex -> next;
}
oddIndex -> next = evenHead;
return head;
}
void insertAtNode(node * & head, int data) {
node * n = new node(data);
n -> next = head;
head = n;
}
void print(node * head) {
while (head != NULL) {
cout << head -> data << "->";
head = head -> next;
}
}
int main() {
node * head = NULL;
// It could be possible that the head node contains NULL Value.
insertAtNode(head, 5);
insertAtNode(head, 8);
insertAtNode(head, 3);
insertAtNode(head, 1);
insertAtNode(head, 2);
print(head);
cout << endl;
segregateList(head);
print(head);
} การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น
ผลลัพธ์
2->3->5->1->8->
รายการเชื่อมโยงที่กำหนดคือ 2->1->3->8->5-> หลังจากแยกรายการที่เชื่อมโยงแล้ว มันจะสร้างผลลัพธ์เป็น 2->3->5->1->8->.
